Pagini recente » Cod sursa (job #1965914) | Cod sursa (job #1215753) | Cod sursa (job #2835048) | Cod sursa (job #2836947) | Cod sursa (job #1044461)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct point {
int x, y;
} P[888];
vector <int> Bucket[888];
double A[888], B[888], C[888];
int OX[888], xx[888];
int curBucket;
inline bool comp(int i, int j) {
int middle = (OX[i] + OX[i + 1]);
double y1 = (-2 * C[i] - A[i] * middle) / B[i];
middle = (OX[j] + OX[j + 1]);
double y2 = (-2 * C[j] - A[j] * middle) / B[j];
return y2 - y1 > 0.000001;
}
bool onLine;
inline int ccw(point A, point B, point C) {
return (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
}
bool check(int x0, int y0, int curLine) {
point tmp; tmp.x = x0; tmp.y = y0;
onLine = 0;
if (ccw(tmp, P[curLine], P[curLine + 1]) == 0)
onLine = 1;
double lineY = (-C[curLine] - A[curLine] * x0) / B[curLine];
return (y0 - lineY >= 0.00001 || y0 == lineY);
}
int main() {
freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
int N, M;
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; ++i) {
scanf("%d%d", &P[i].x, &P[i].y);
xx[++xx[0]] = P[i].x;
}
P[N + 1] = P[1];
for (int i = 1; i <= N; ++i) {
A[i] = P[i].y - P[i + 1].y;
B[i] = P[i + 1].x - P[i].x;
C[i] = P[i].x * P[i + 1].y - P[i].y * P[i + 1].x;
}
sort(xx + 1, xx + xx[0] + 1);
OX[++OX[0]] = xx[1];
for (int i = 2; i <= xx[0]; ++i)
if (xx[i] != OX[OX[0]])
OX[++OX[0]] = xx[i];
for (int i = 1; i <= OX[0]; ++i) {
curBucket = i;
for (int j = 1; j <= N; ++j)
if (min(P[j].x, P[j + 1].x) <= OX[i] && OX[i] < max(P[j].x, P[j + 1].x))
Bucket[i].push_back(j);
sort(Bucket[i].begin(), Bucket[i].end(), comp);
}
int res = 0;
while (M--) {
int x0, y0;
scanf("%d%d", &x0, &y0);
if (x0 < OX[1] || x0 > OX[OX[0]])
continue;
curBucket = 0;
for (int step = 10; step >= 0; --step)
if (curBucket + (1 << step) <= OX[0] && OX[curBucket + (1 << step)] < x0)
curBucket += (1 << step);
int j = 0;
for (int step = 10; step >= 0; --step)
if (j + (1 << step) <= Bucket[curBucket].size() && check(x0, y0, Bucket[curBucket][j + (1 << step) - 1]))
j += (1 << step);
if (j % 2 == 1 || onLine == 1)
++res;
}
printf("%d", res);
return 0;
}