Pagini recente » Cod sursa (job #2306472) | Cod sursa (job #93515) | Cod sursa (job #873018) | Cod sursa (job #1182609) | Cod sursa (job #1044459)
#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]);
int y1 = (-2 * C[i] - A[i] * middle) / B[i];
middle = (OX[j] + OX[j + 1]);
int y2 = (-2 * C[j] - A[j] * middle) / B[j];
return y1 < y2;
}
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;
int lineY = (-C[curLine] - A[curLine] * x0) / B[curLine];
return 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, lg;
for (lg = 0; (1 << lg) <= N; ++lg); --lg;
while (M--) {
int x0, y0;
scanf("%d%d", &x0, &y0);
if (x0 < OX[1] || x0 > OX[OX[0]])
continue;
curBucket = 0;
for (int step = lg; step >= 0; --step)
if (curBucket + (1 << step) <= OX[0] && OX[curBucket + (1 << step)] < x0)
curBucket += (1 << step);
int j = 0;
for (int step = lg; 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;
}