题意:同POJ2318
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
struct point {
int x, y;
};
struct Node {
point Low, High;
}line[5010];
int Num[5010];
int par[5010];
bool cmp(Node A, Node B) {
return A.High.x < B.High.x;
}
bool is_right(int x, int y, Node ln) {
point P = ln.High;
point Q = ln.Low;
if (((P.x - x)*(Q.y - y) - (P.y - y)*(Q.x - x)) > 0)
return true;
else
return false;
}
void bin_seach(int x, int y, int n) {
int left = 1;
int right = n;
while (left <= right) {
int mid = (left + right) / 2;
if (is_right(x, y, line[mid])) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
par[left]++;
}
int main() {
int n, m, i, j, x1, x2, y1, y2;
while (scanf("%d", &n), n) {
memset(par, 0, sizeof(par));
memset(Num, 0, sizeof(Num));
scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
for (int i = 1; i <= n; i++) {
scanf("%d", &line[i].High.x);
line[i].High.y = y1;
scanf("%d", &line[i].Low.x);
line[i].Low.y = y2;
}
sort(line + 1, line + 1 + n, cmp);
int xx, yy;
int t = m;
while (m--) {
scanf("%d%d", &xx, &yy);
bin_seach(xx, yy, n);
}
for (int i = 1; i <= n + 1; i++) {
if (par[i])
Num[par[i]]++;
}
printf("Box\n");
for (int i = 1; i <= t; i++) {
if (Num[i])
printf("%d: %d\n", i, Num[i]);
}
}
return 0;
}