[Login|Register]
Problems

Status

Rank

Problem 1256
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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.4ms with 1 query(s).