题意：同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;}
