Pagini recente » Cod sursa (job #1491981) | Cod sursa (job #2337344) | Cod sursa (job #929960) | Cod sursa (job #53167) | Cod sursa (job #346977)
Cod sursa(job #346977)
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 810
int n, m, t, sol;
int f[MAX_N], len[MAX_N];
double dm, dn;
struct punct {
int x, y;
} A[MAX_N], P;
struct latura {
double y1, y2;
};
latura v[MAX_N][MAX_N];
void cit() {
freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d %d", &A[i].x, &A[i].y);
A[n + 1] = A[1];
//gasesc numarul de fasii
for (int i = 1; i <= n; i++) f[i] = A[i].x;
sort(f + 1, f + n + 1);
t = 1;
for (int i = 1; i < n; i++)
if (f[i] != f[i + 1])
f[++t] = f[i + 1];
}
inline int cmp(latura P, latura Q) {
return P.y1 + P.y2 < Q.y1 + Q.y2;
}
void solve() {
for (int i = 1; i <= n; i++)
if (A[i].x != A[i + 1].x) { //am luat o latura i
dm = 1.0 * (A[i + 1].y - A[i].y) / (A[i + 1].x - A[i].x);
dn = A[i].y - dm * A[i].x;
for (int j = 1; j < t; j++)
if ((A[i].x <= f[j] && f[j + 1] <= A[i + 1].x) || (A[i + 1].x <= f[j] && f[j + 1] <= A[i].x)) {
//intersectez fasiile (f[j], f[j + 1]) cu latura (j, j + 1)
latura lat;
lat.y1 = dm * f[j] + dn;
lat.y2 = dm * f[j + 1] + dn;
v[j][++len[j]] = lat;
}
}
for (int i = 1; i < t; i++)
if (len[i])
sort(v[i] + 1, v[i] + len[i] + 1, cmp);
}
inline double det(int x1, double y1, int x2, double y2, int x3, int y3) {
return x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2;
}
int binary_search(int k) {
int st = 0, dr = len[k] + 1, mid = 0, poz = 0;
while (st + 1 < dr) {
mid = (st + dr) >> 1;
double val = det(f[k], v[k][mid].y1, f[k + 1], v[k][mid].y2, P.x, P.y);
if (val == 0)
return 1;
if (val > 0) {
if (mid > poz) poz = mid;
st = mid;
}
else dr = mid;
}
return poz % 2;
}
void write() {
for (int i = 1; i <= m; i++) {
scanf("%d %d", &P.x, &P.y);
int st = 0, dr = t, mid = 0;
while (st + 1 < dr) {
mid = (st + dr) >> 1;
if (f[mid] <= P.x && P.x <= f[mid + 1]) {
if (P.x == f[mid] || P.x == f[mid + 1]) {
if (binary_search(mid - 1) || binary_search(mid) || binary_search(mid + 1)) sol++;
break;
}
sol += binary_search(mid);
break;
}
else if (f[mid] > P.x) dr = mid;
else st = mid;
}
}
printf("%d\n", sol);
}
int main() {
cit();
solve();
write();
return 0;
}