·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://poj.org/problem?id=2318
这题是计算几何题，需要用到叉积判断点在线段的左边还是右边。
暴力的话n^2的复杂度应该会超时，这里用了二分的方法。把地图的左右边界各自作为一条直线插入，并且考虑到存在点落在边界的情况，这两条新加的直线要对应向地图外偏移一点。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
const double eps = 1e-8;
const double inf = 1e20;
int sgn(double x) {
if (fabs(x) < eps) return 0;
if (x < 0) return -1;
else return 1;
}
struct Point {
double x, y;
Point() {}
Point(double _x, double _y) {
x = _x;
y = _y;
}
void input() {
scanf("%lf%lf", &x, &y);
}
Point operator - (const Point &b) const {
return Point(x - b.x, y - b.y);
}
double operator ^ (const Point &b) const {
return x * b.y - y * b.x;
}
};
struct Line {
Point s, e;
Line() {}
Line(Point _s, Point _e) {
s = _s;
e = _e;
}
void input(int x1, int y1, int x2, int y2) {
s.x = x1;
s.y = y1;
e.x = x2;
e.y = y2;
}
int relation(Point p) {
int c = sgn((p-s) ^ (e-s));
if (c < 0) return 1;
else if (c > 0) return 2;
else return 3;
}
};
const int maxn = 5000 + 10;
int n, m;
Line lines[maxn];
int cnt[maxn];
bool check(int mid, Point now) {
if (lines[mid].relation(now) == 2) return 1;
else return 0;
}
int main() {
int x1, y1, x2, y2;
int U, L;
while(scanf("%d", &n)!=EOF && n) {
memset(cnt, 0, sizeof(cnt));
scanf("%d", &m);
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
lines[0].input(x1-1, y1, x1-1, y2);
lines[n+1].input(x2+1, y1, x2+1, y2);
for(int i = 1; i <= n; i++) {
scanf("%d%d", &U, &L);
lines[i].input(U, y1, L, y2);
}
for(int i = 0; i < m; i++) {
Point now;
now.input();
int l = 0, r = n + 1;
while(l < r-1) {
int mid = (l+r) >> 1;
if (check(mid, now)) r = mid;
else l = mid;
}
cnt[l]++;
}
for(int i = 0; i <= n; i++)
printf("%d: %d\n", i, cnt[i]);
printf("\n");
}
}