题目 1944:
蓝桥杯算法提高VIP-Air Traffic Control
时间限制: 2s
内存限制: 192MB 提交: 2 解决: 0
题目描述
为了避免空中相撞，大部分商业航班都被地面航空管制中心使用雷达跟踪其位置来监控。在这个问题中，你会被给予一组飞机和一组控制中心的信息，并计算出飞机是如何被控制中心监控的（这句话的意思参考输入描述：即计算恰好被K个控制中心监控的飞机数目），飞机的位置用(x,y)坐标表示，基于此题的目的，无视飞机的高度（海拔）。
一个给定的控制中心能够监控的飞机数量因设备和工作人员的改变而时刻变化。在任一时刻，每一个控制中心会尽可能地监控更多的飞机，它会按照如下优先级选择其监控的飞机：1.离这个控制中心欧几里得距离比较近的优于比较远的。2.若两架飞机到控制中心的距离相同，那么选择其中往北更远的(y坐标轴正方向)。3.如果两架飞机的距离和y坐标都相同，优先选择往东更远的（x坐标正方向）。（补充说明：也就是说在距离相同的情况下，先比较y坐标，y坐标大的优先级高，若y坐标依旧相同，x坐标大的优先级高。数据会保证没有任意两个飞机的坐标相同。）
在任意时刻，每一个控制中心都有一个圆形“控制范围”，其半径等于其所监控的最远的那架飞机的距离。所有在控制范围内的飞机都被该控制中心监控，但是在控制范围边界上的飞机可能或可能不被控制中心监控，这取决于控制中心的容量和以上列出的优先级。
你不会被告知控制中心的位置,取而代之的，对于每个控制中心，你会被告知它当前监控的飞机个数，以及其监控范围边界上的两点，用这些信息，你能计算出控制中心的位置，以及决定哪些飞机被其监控。如果数据包含多种可能的监控范围，你应该选择包含了靠北最远的那架飞机的，通过先选择靠北最远的再选择靠东最远的打破平局（——这段话的意思你可以这么认为：如果有多种可能的控制范围以及对应的控制中心位置满足输入要求，那么我们这么来判定：将飞机按照y坐标从大到小，y坐标相同的按照x从大到小排序，然后依次考虑，如果有架飞机在控制范围A内，而其不在控制范围B内，则我们会选择A而不是B。注意，若两个控制范围监控的飞机的集合相同，可以任意选择一个，因为这不影响答案）。
下面这张图展示了两个控制中心和四架飞机的情况。每个控制中心用一个圆形控制区域和这个区域中的两个点表示，用A和B标记。P1，P2，P3，P4标记了四架飞机。在这个例子中，飞机P1和P4都被一个单独的控制中心监视，而P3被两个控制中心监控，但P2却没有被任何一个控制中心监控。
一个给定的控制中心能够监控的飞机数量因设备和工作人员的改变而时刻变化。在任一时刻，每一个控制中心会尽可能地监控更多的飞机，它会按照如下优先级选择其监控的飞机：1.离这个控制中心欧几里得距离比较近的优于比较远的。2.若两架飞机到控制中心的距离相同，那么选择其中往北更远的(y坐标轴正方向)。3.如果两架飞机的距离和y坐标都相同，优先选择往东更远的（x坐标正方向）。（补充说明：也就是说在距离相同的情况下，先比较y坐标，y坐标大的优先级高，若y坐标依旧相同，x坐标大的优先级高。数据会保证没有任意两个飞机的坐标相同。）
在任意时刻，每一个控制中心都有一个圆形“控制范围”，其半径等于其所监控的最远的那架飞机的距离。所有在控制范围内的飞机都被该控制中心监控，但是在控制范围边界上的飞机可能或可能不被控制中心监控，这取决于控制中心的容量和以上列出的优先级。
你不会被告知控制中心的位置,取而代之的，对于每个控制中心，你会被告知它当前监控的飞机个数，以及其监控范围边界上的两点，用这些信息，你能计算出控制中心的位置，以及决定哪些飞机被其监控。如果数据包含多种可能的监控范围，你应该选择包含了靠北最远的那架飞机的，通过先选择靠北最远的再选择靠东最远的打破平局（——这段话的意思你可以这么认为：如果有多种可能的控制范围以及对应的控制中心位置满足输入要求，那么我们这么来判定：将飞机按照y坐标从大到小，y坐标相同的按照x从大到小排序，然后依次考虑，如果有架飞机在控制范围A内，而其不在控制范围B内，则我们会选择A而不是B。注意，若两个控制范围监控的飞机的集合相同，可以任意选择一个，因为这不影响答案）。
下面这张图展示了两个控制中心和四架飞机的情况。每个控制中心用一个圆形控制区域和这个区域中的两个点表示，用A和B标记。P1，P2，P3，P4标记了四架飞机。在这个例子中，飞机P1和P4都被一个单独的控制中心监视，而P3被两个控制中心监控，但P2却没有被任何一个控制中心监控。
输入格式
输入包含多组测试数据，每个数据第一行包括两个正整数NP(0<NP<100)和NC(0<NC<10)，分别表示了飞机的个数和控制中心的个数。接下来NP行，每行两个浮点数表示一架飞机的(x,y)坐标。再接下来NC行，每行描述一个控制中心。首先是一个位于0到NP的正整数（包含0和NP），表示被该控制中心监控的飞机个数，然后是两对浮点数表示监控范围边界上的两个位置的(x,y)坐标（两个位置不会相同，而且也不会与飞机坐标重合）。注意：若两个点之间的距离小于0.00001，你应该将其视为一个点。
输入以两个0结束。
输入以两个0结束。
输出格式
对于每组数据，计算出被0个控制中心监控的飞机个数，被1个控制中心监控的飞机个数等等，直到被NC个控制中心监控的飞机个数。首先输出数据组号，然后接下来NC+1个数，序列中第ith数表示被i-1个控制中心监控的飞机个数。如果某个控制中心不存在相符合的监控范围，那么输出"Impossible"而不是相应的序列。使用样例中给定的输出格式，然后每组数据之后都要输出一个空行。
（关于输出格式，请注意冒号之后有两个空格，每个序列中每两个数之间有两个空格，序列的行末有两个空格，Impossible后没有空格，每组数据输出占两行。）
（关于输出格式，请注意冒号之后有两个空格，每个序列中每两个数之间有两个空格，序列的行末有两个空格，Impossible后没有空格，每组数据输出占两行。）
样例输入
4 2 3.0 0.0 0.0 0.0 1.6 2.8 2.0 1.0 2 1.0 2.0 2.0 0.0 2 2.0 2.0 4.0 2.0 2 1 0.0 0.5 0.0 -0.5 0 -1.0 0.0 1.0 0.0 0 0
样例输出
Trial 1: 1 2 1 Trial 2: Impossible