Pagini recente » Cod sursa (job #2221404) | Cod sursa (job #828511) | Cod sursa (job #1088669) | Cod sursa (job #145378) | Cod sursa (job #1088666)
#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;
struct comp {
inline bool operator () (int i, int j) {
int middle = OX[curBucket] + OX[curBucket + 1];
double y1 = (-2.0 * C[i] - A[i] * middle) / B[i];
double y2 = (-2.0 * C[j] - A[j] * middle) / B[j];
return y2 - y1 > 0.000001;
}
};
bool onLine;
bool check(int x0, int y0, int curLine) {
if (A[curLine] * x0 + B[curLine] * y0 + C[curLine] == 0)
onLine = 1;
double 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;
while (M--) {
int x0, y0;
scanf("%d%d", &x0, &y0);
if (x0 < OX[1] || x0 > OX[OX[0]])
continue;
curBucket = onLine = 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\n", res);
return 0;
}