Cod sursa(job #385437)

Utilizator ErgoVicol Sergiu Constantin Ergo Data 22 ianuarie 2010 18:34:58
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.21 kb
//Poligon - lista lui wefgef (infoarena)

#include <fstream>
#include <algorithm>
#include <vector>

#define NMAX 800
#define pb push_back

using namespace std;

ifstream fin("poligon.in");
ofstream fout("poligon.out");


/* Structuri */

struct punct
{
	int x, y;
};


int N, M, benzi[NMAX], nrBenzi, Ban, Total; //Benzi[i] va contine limita din stanga a benzii I, iar Benzi[i+1] limita din dreapta
punct poligon[NMAX];

vector<int> drepteBanda[NMAX];

inline double pos(double a)
{
	if (a < 0) return -a;
	else return a;
}

inline double middleY(double mX, int i) /* face un calcul complicat */ 
{
	return pos( (mX - poligon[i].x)*(poligon[i+1].y - poligon[i].y)/(poligon[i+1].x - poligon[i].x) + poligon[i].y  );
}

int sortareBenzi(int a, int b) /* sortareBenzi sorteaza dreptele fiecarei benzi pe orizontala */
{
	double mX;
	mX = (double) ( benzi[Ban] + benzi[Ban + 1] ) / 2;
	
	if ( middleY(mX,a) < middleY(mX,b) ) 
		return 1;
	else return 0;
}

int cautaBanda(int xC)
{
	int st = 1, end = nrBenzi - 1, m;
	m = (st + end) / 2;
	while (xC < benzi[m] || xC > benzi[m+1])
	{
		if (xC > benzi[m+1]) st = m+1;
		if (xC < benzi[m]) end = m - 1;
		m = (st + end) / 2;
	}
	return m;
}

int cautaPeOrizontala(int xC, int yC)
{
	int st = 0, end = drepteBanda[Ban].size() -1 , m;
	m = (st + end) / 2;
	
	while (!(middleY(xC, drepteBanda[Ban][m]) <= yC && middleY(xC, drepteBanda[Ban][m+1]) > yC))
	{
		if (middleY(xC, drepteBanda[Ban][m]) > yC) end = m - 1;
		if (middleY(xC, drepteBanda[Ban][m+1]) <= yC) st = m + 1;
		m = (st + end) / 2;
	}		
	
	return m;
}

int main()
{
	int i, j, xC, yC, posO; //Varibilele sclav
	
	benzi[0] = -1;
	
	fin >>N >>M;
	
	for(i = 1; i <= N; i++)
		fin >>poligon[i].x >>poligon[i].y;

	poligon[N+1] = poligon[1];
	
	/* Realizarea celor K benzi */
	for (i = 1; i <= N; i++)
		benzi[i] = poligon[i].x;
	
	sort(benzi + 1, benzi + N + 1);
	
	for (i = 1; i <= N; i++) //Eliminam coordonatele care se repeta 
		if (benzi[i] != benzi[i-1])
			benzi[++nrBenzi] = benzi[i];
		
	for (i = 1; i <= N; i++) //Vedem ce drepte apartin fiecarei benzi [O(n^2)]
		for (j = 1; j < nrBenzi; j++)
			if ( ((poligon[i].x <= benzi[j] && poligon[i+1].x >= benzi[j+1]) || (poligon[i].x >= benzi[j+1] && poligon[i+1].x <= benzi[j])) )
				drepteBanda[j].pb(i);
			
	/* Sortarea dupa mijloc a dreptelor, pe banda */
	for (Ban = 1; Ban < nrBenzi; Ban++)
		sort(drepteBanda[Ban].begin(), drepteBanda[Ban].end(), sortareBenzi);
		
	
	/* Am terminat toate aranjamentele, urmeaza citirea variabilelor si aflarea */
	
	for (j = 1; j <= M; j++)
	{
		fin >>xC >>yC;
		
		if (xC < benzi[1] || xC > benzi[nrBenzi]) 
			fout << "0\n";
		else
		{
			if (xC == benzi[1])
				Ban = 1;
			else
				Ban = cautaBanda(xC);
			
			if (!( (float) yC < middleY(xC, drepteBanda[Ban].front()) || (float) yC > middleY(xC, drepteBanda[Ban].back())) )
			{
				if ( (float) yC == middleY(xC, drepteBanda[Ban].back() ) )
					Total++;
				else
				{
					posO = cautaPeOrizontala(xC, yC);
					if ( (float) yC == middleY(xC, drepteBanda[Ban][posO]) ) 
						Total++;
					else
						Total += (posO + 1)%2;
				}
			}
		}
	}
	fout << Total;
	fout.close();
	return 0;
}