#317. [国家集训队] JZPFAR

[国家集训队] JZPFAR

[国家集训队] JZPFAR

题目描述

平面上有 nn 个点。现在有 mm 次询问,每次给定一个点 (px,py)(px, py) 和一个整数 kk,输出 nn 个点中离 (px,py)(px, py) 的距离第 kk 大的点的标号。如果有两个(或多个)点距离 (px,py)(px, py) 相同,那么认为标号较小的点距离较大。

输入格式

第一行,一个整数 nn,表示点的个数。

下面 nn 行,每行两个整数 xi,yix_i,y_i,表示 nn 个点的坐标。点的标号按照输入顺序,分别为 1n1\ldots n

下面一行,一个整数 mm,表示询问个数。

下面 mm 行,每行三个整数 pxi,pyi,kipx_i,py_i,k_i,表示一个询问。

输出格式

mm 行,每行一个整数,表示相应的询问的答案。

样例 #1

样例输入 #1

3
0 0
0 1
0 2
3
1 1 2
0 0 3
0 1 1

样例输出 #1

3
1
1

提示

数据规模与约定

  • 50%50\% 的数据中,nn 个点的坐标在某范围内随机分布。
  • 100%100\% 的数据中,1n1051\le n\le 10^51m1041\le m\le 10^41k201\le k\le 20109xi,yi,pxi,pyi109-10^9\le x_i,y_i,px_i,py_i\le 10^9nn 个点中任意两点坐标不同,mm 个询问的点的坐标在某范围内随机分布。