#P2093. [国家集训队] JZPFAR

[国家集训队] JZPFAR

题目背景

原《零件分组》见 P1233。

题目描述

平面上有 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 行,每行一个整数,表示相应的询问的答案。

3
0 0
0 1
0 2
3
1 1 2
0 0 3
0 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 个询问的点的坐标在某范围内随机分布。