Pagini recente » Cod sursa (job #150068) | Cod sursa (job #1132394) | Cod sursa (job #1382589) | Cod sursa (job #2928033) | Cod sursa (job #842988)
Cod sursa(job #842988)
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define PII pair<int, int>
#define pb push_back
#define x first
#define y second
#define nmax 810
PII A[nmax], crtP;
int B[nmax], C[nmax], X[nmax], Y[nmax], Z[nmax], N, M, ans, ok, left, right, step;
double XX[nmax], ZZ[nmax];
vector<int> Banda[nmax];
bool cmp(int ind1, int ind2)
{
return (XX[ind1] * (left + right) + 2 * ZZ[ind1] < XX[ind2] * (left + right) + 2 * ZZ[ind2]);
}
bool Check(int ind, PII P)
{
if(X[ind] * P.x + Y[ind] * P.y + Z[ind] == 0) ok = 1;
return (P.y >= XX[ind] * P.x + ZZ[ind]);
}
int main()
{
freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
int i, j;
scanf("%i %i", &N, &M);
for(i = 1; i <= N; i++)
scanf("%i %i", &A[i].x, &A[i].y);
A[N + 1] = A[1];
for(i = 1; i <= N; i++)
{
X[i] = (A[i + 1].y - A[i].y);
Y[i] = (A[i].x - A[i + 1].x);
Z[i] = (A[i].y * A[i + 1].x - A[i].x * A[i + 1].y);
XX[i] = -1.0 * X[i] / Y[i];
ZZ[i] = -1.0 * Z[i] / Y[i];
}
for(i = 1; i <= N; i++)
B[i] = A[i].x;
sort(B + 1, B + N + 1);
C[++C[0]] = B[1];
for(i = 2; i <= N; i++)
if(B[i] != B[i - 1])
C[++C[0]] = B[i];
for(i = 1; i <= C[0]; i++)
{
for(j = 1; j <= N; j++)
if(min(A[j].x, A[j + 1].x) <= C[i] && C[i] < max(A[j].x, A[j + 1].x))
Banda[i].pb(j);
left = C[i], right = C[i + 1];
sort(Banda[i].begin(), Banda[i].end(), cmp);
}
for(; M; M --)
{
scanf("%i %i", &crtP.x, &crtP.y);
if(C[1] <= crtP.x && crtP.x <= C[C[0]])
{
ok = 0;
step = 1024, i = 0, j = 0;
for(; step; step /= 2)
if(i + step <= C[0] && C[i + step] < crtP.x)
i += step;
for(step = 1024; step; step /= 2)
if(j + step <= Banda[i].size() && Check(Banda[i][j + step - 1], crtP))
j += step;
ans = ans + max(j % 2, ok);
}
}
printf("%i\n", ans);
return 0;
}