http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1302. JZPFAR(顾昱洲)
时间限制:5.0s   内存限制:256.0MB  
总提交次数:573   AC次数:147   平均分:40.48
将本题分享到:
   
 
问题描述
  平面上有n个点。现在有m次询问,每次给定一个点(px, py)和一个整数k,输出n个点中离(px, py)的距离第k大的点的标号。如果有两个(或多个)点距离(px, py)相同,那么认为标号较小的点距离较大。
输入格式
  第一行,一个整数n,表示点的个数。
  下面n行,每行两个整数x_i, y_i,表示n个点的坐标。点的标号按照输入顺序,分别为1..n。
  下面一行,一个整数m,表示询问个数。
  下面m行,每行三个整数px_i, py_i, k_i,表示一个询问。
输出格式
  m行,每行一个整数,表示相应的询问的答案。
样例输入
3
0 0
0 1
0 2
3
1 1 2
0 0 3
0 1 1
样例输出
3
1
1
数据规模和约定
  50%的数据中,n个点的坐标在某范围内随机分布。
  100%的数据中,n<=10^5, m<=10^4, 1<=k<=20,所有点(包括询问的点)的坐标满足绝对值<=10^9,n个点中任意两点坐标不同,m个询问的点的坐标在某范围内随机分布。