Pagini recente » Cod sursa (job #1225863) | Cod sursa (job #938969) | Cod sursa (job #409188) | Cod sursa (job #829938) | Cod sursa (job #346827)
Cod sursa(job #346827)
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 810
#define pb push_back
int n, m, sol, t;
int f[MAX_N], len[MAX_N];
int prec[60010];
struct punct {
int x, y;
} v[MAX_N], P;
struct latura {
int x1, x2;
double y1, y2;
} l;
vector <latura> A[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", &v[i].x, &v[i].y);
f[i] = v[i].x;
}
sort(f + 1, f + n + 1);
f[t = 1] = f[1];
for (int i = 1; i < n; i++)
if (f[i] != f[i + 1])
f[++t] = f[i + 1];
}
void intersect(int k) {
//intersectez latura l cu f[k] si f[k + 1]
double m = 1.0 * (l.y2 - l.y1) / (l.x2 - l.x1);
double n = l.y1 - m * l.x1;
l.x1 = f[k];
l.y1 = (double) m * f[k] + n;
l.x2 = f[k + 1];
l.y2 = (double) m * f[k + 1] + n;
A[k].pb(l);
}
inline int cmp(latura P, latura Q) {
return P.y1 + P.y2 < Q.y1 + Q.y2;
}
void solve() {
//calculez ce segmente o sa contina muchiile (i, i + 1), 0 < i < k
v[n + 1] = v[1];
for (int i = 1; i < t; i++) {
for (int j = 1; j <= n; j++) {
l.x1 = v[j].x; l.y1 = v[j].y;
l.x2 = v[j + 1].x; l.y2 = v[j + 1].y;
if (v[j].x > v[j + 1].x || (v[j].x == v[j + 1].x && v[j].y > v[j + 1].y)) {
l.x1 = v[j + 1].x; l.y1 = v[j + 1].y;
l.x2 = v[j].x; l.y2 = v[j].y;
}
if (l.x1 != l.x2 && f[i] >= l.x1 && f[i + 1] <= l.x2)
intersect(i);
}
}
for (int i = 1; i < t; i++) {
sort(A[i].begin(), A[i].end(), cmp);
len[i] = A[i].size();
prec[f[i]] = i;
}
for (int i = 0; i <= 60000; i++)
if (!prec[i]) prec[i] = prec[i - 1];
}
inline double det(int x1, double y1, int x2, double y2, int x3, int y3) {
return (double) x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2;
}
void binary_search(int k) {
int st = -1, dr = len[k], mid = 0;
int ret = -1;
while (st + 1 < dr) {
mid = (st + dr) / 2;
double val = det(A[k][mid].x1, A[k][mid].y1, A[k][mid].x2, A[k][mid].y2, P.x, P.y);
if (val == 0) {
sol++;
return;
}
if (val > 0) {
if (mid > ret)
ret = mid;
st = mid;
}
else dr = mid;
}
sol += (ret + 1) % 2;
}
void write() {
for (int i = 1; i <= m; i++) {
scanf("%d %d", &P.x, &P.y);
//caut binar sa vad cate segmente sunt sub punct
if (prec[P.x]) binary_search(prec[P.x]);
}
printf("%d\n", sol);
}
int main() {
cit();
solve();
write();
return 0;
}