acwing-2983. 玩具(计算几何)

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

计算玩具收纳盒中，每个分区内的玩具数量。

约翰的父母有一个烦恼—-约翰每次玩完玩具以后总会将玩具乱扔。

他们为约翰准备了一个长方形的玩具收纳盒，用来放他的玩具。

但是约翰非常调皮，每次都非常随意的将玩具扔进盒子中，使得所有玩具都随意混在一起，这让约翰难以找到他喜欢的玩具。

对此，约翰的父母想出了一个对策，用若干个纸板将收纳盒分隔成若干个分区，这样至少扔到不同分区的玩具之间还是能分开的。

下面是一个收纳盒的俯视图示例。

1.jpg

你的任务是，每当约翰将玩具扔进收纳盒中时，确定每个分区中有多少个玩具。

输入格式
本题包含多组测试数据。

对于每组数据，第一行包含 6 个整数 n,m,x1,y1,x2,y2，表示共有 n 个纸板，m 个玩具，收纳盒的左上角坐标为 (x1,y1)，右下角坐标为 (x2,y2)。

接下来 n 行，每行包含两个整数 Ui,Li，表示第 i 个纸板的两端点坐标分别为 (Ui,y1) 和 (Li,y2)。数据保证纸板之间不相交，且按照从左至右顺序依次给出。

接下来 m 行，每行包含两个整数 Xj,Yj，表示第 j 个玩具的位置坐标。玩具的给出顺序是随机的。数据保证玩具不会恰好落在纸板上，也不会落在盒子外。

输入由包含单个 0 的一行结束。

输出格式
对于每组数据，输出 n+1 行。

n 个纸板将收纳盒划分为了 n+1 个分区，从左到右编号为 0∼n。

按照分区编号从小到大的顺序，每行输出一行信息 i: j，其中 i 表示分区编号，j 表示分区内玩具数量。

每组数据之间，用空行隔开。

数据范围
每个测试点最多包含 10 组数据。
1≤n,m≤5000,
所有坐标取值范围 [−105,105]。

输入样例：
5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
 5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10
0
输出样例：
0: 2
1: 1
2: 1
3: 1
4: 0
5: 1

0: 2
1: 2
2: 2
3: 2
4: 2

注意
如示例所示，落在盒子边缘的玩具也算在盒子内。
题解
二分+点与直线位置关系