poj 2398 Toy Storage

题目描述：http://www.poj.org/problem?id=2398

该题算是poj 2318 的加强版，poj 2318 的解题报告见：
http://scott--------.iteye.com/blog/1013250

与2318 相比有一下不同：
    1.输入的分割线无序
    2.输出要求统计玩具的分布情况，假设m 个分区中都正好有t 个玩具，
      要就输出m1: t1, m2: t2,...。按m 大小升序。

#include <cstdio>
#include <algorithm>
using namespace std;

struct point {
	int x,y;
};

struct line {
	point a,b;
};

int xmult(line seg, point p) {
	return (seg.a.x - p.x) * (p.y - seg.b.y) -
			(p.x - seg.b.x) * (seg.a.y - p.y);
}

//对玩具位置进行排序
bool comp(point p1, point p2) {
	if(p1.x != p2.x)
		return p1.x < p2.x;
	return p1.y < p2.y;
}

//对输出的分割线进行排序
bool seg_comp(line seg1, line seg2) {
    return seg1.a.x < seg2.a.x;
}

int main() {
	//freopen("in.txt", "r", stdin);
	int n, m;
	point lu, rl;
	point toys[1005];
	line segs[1005];
	int cnt[1005];
	while(scanf("%d", &n) != EOF) {
		if(n == 0)
			break;
		for(int i = 0; i < n  + 1; i++)
			cnt[i] = 0;
		scanf("%d %d %d %d %d", &m, &lu.x, &lu.y, &rl.x, &rl.y);
		segs[0].a = lu;
		segs[0].b.x = lu.x;
		segs[0].b.y = rl.y;
		segs[n + 1].a.x = rl.x;
		segs[n + 1].a.y = lu.y;
		segs[n + 1].b = rl;
		
		int u, l;
		for(int i = 1; i <= n; i++) {
			scanf("%d %d", &u, &l);
			segs[i].a.x = u;
			segs[i].a.y = lu.y;
			segs[i].b.x = l;
			segs[i].b.y = rl.y;
		}
        sort(segs + 1, segs + n + 1, seg_comp);
		for(int i = 0; i < m; i++)
			scanf("%d %d", &toys[i].x, &toys[i].y);
			
		int k = 0;
        sort(toys, toys + m, comp);
		for(int i = 0; i < m; i++) {
			for(int j = k; j <= n; j++) {    //避免每次都从j == 0 处开始搜索
				if(xmult(segs[j], toys[i]) <= 0
					&& xmult(segs[j + 1], toys[i]) >= 0) {
					cnt[j]++;
                    k = j;  //避免每次都从j == 0 处开始搜索
					break;
				}
			}
		}
        sort(cnt, cnt + n + 1);
		printf("Box\n");
        int i = 0;
        while(cnt[i] == 0)
            i++;
        int count = 1;
        cnt[n + 1] = 0x7fffffff;  //保证最后一组结果的输出
        for(; i <= n; i++) {
            if(cnt[i] != cnt[i + 1]) {
                printf("%d: %d\n", cnt[i], count);
                count = 1;
            }
            else
                count++;
        }
	}
	return 0;
}