P2093 [国家集训队]JZPFAR

    • 238通过
    • 630提交
  • 题目提供者 JOHNKRAM
  • 评测方式 云端评测
  • 标签 K-D Tree WC/CTSC/集训队
  • 难度 NOI/NOI+/CTSC
  • 时空限制 3000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    原《零件分组》见P1233

    题目描述

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

    输入输出样例

    输入样例#1: 复制
    3
    0 0
    0 1
    0 2
    3
    1 1 2
    0 0 3
    0 1 1
    输出样例#1: 复制
    3
    1
    1

    说明

    50%的数据中,n个点的坐标在某范围内随机分布。

    100%的数据中,n<=10^5, m<=10^4, 1<=k<=20,所有点(包括询问的点)的坐标满足绝对值<=10^9,n个点中任意两点坐标不同,m个询问的点的坐标在某范围内随机分布。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。