Pagini recente » Cod sursa (job #111019) | Cod sursa (job #2430995) | Cod sursa (job #489341) | Cod sursa (job #47285) | Cod sursa (job #385437)
Cod sursa(job #385437)
//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;
}