| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem G
Dota
Time Limit: 1000ms
Memory Limit: 65536kb Description
that was my plan~you thought of that~ your soul is mine i hunger~deathrageous~die~ 小W大二决定去玩电子竞技了，他选择了dota，而dota中他最喜欢的英雄是影魔。现在小W操纵了两个影魔，影魔在一个二维世界中，在其中有很多英雄，每个影魔以自己为中心画一个圆，每个圆的面积大小等于该影魔的灵魂量(为了需要，两个影魔总的灵魂量是个实数)，则在圆内的英雄就死掉了。小W一共拥有T灵魂量，他可以给两个影魔任意分配灵魂量，但要使两个影魔的灵魂量之和为T。现在小W想知道，如果用最好的灵魂量分配方案，至少有多少英雄可以逃生？ 于是小W找到了你，给你两个影魔的坐标（X1，Y1）与（X2，Y2）和N个英雄的位置，和小W拥有的灵魂量，问至少有多少英雄可以逃生？ Input
第一行一个整数M，表示有M个Cases(M<=20)对于每个Case： 第一行一个正整数N，表示有N个英雄（N<=1e5） 第二行5个实数X1 Y1 X2 Y2 T，表示两个影魔的坐标，和小W的灵魂量总数。 之后N行每行两个实数X,Y,表示每个英雄的坐标。 保证所有坐标范围在[-100,100]之内，T>=0.数据中小数位数不超过3位，为防止精度问题，取pi=3.141。 PS：因为数据随机产生，所以不保证每个英雄的坐标不同。 Output
对于每个Case，输出一个整数A后换行，表示至少有A个英雄可以逃生。
Sample Input
1 10 -60.415 20.280 -30.538 -79.484 15733.388 79.539 -6.365 90.572 -35.898 -75.111 22.892 -69.956 33.638 -78.978 25.319 59.304 -80.334 -64.226 -1.445 -16.371 -15.285 -20.001 -67.472 87.740 96.172 Sample Output
4 |