#2311. 公园
公园
公园
题目描述
CCF NOI 2024 四川省代表队评测活动 第一试 公园(park) 公园(park) 【题目描述】 某处公园可以看做是一个无限大的二维平面。公园内一共有 𝑛 盏路灯,标号分别为 1, 2, …, 𝑛。每盏路灯可以看做是二维平面上的一个点。 小 A 和他的妈妈来到了这座公园内游玩。妈妈告诉小 A 不能跑得太远,所以他只能在一 个左下角为 (0, 0),右上角为 (𝑋, 𝑌) 的矩形区域内游玩(小 A 可以到达矩形边界)。 小 A 对 𝑖 号路灯非常感兴趣。他想要在矩形内找到一个位置(设为点 𝑃),然后设第 𝑘 (1 ≤𝑘≤𝑛)盏路灯距离 𝑃 的距离为 𝑑𝑘(𝑃)。之后,如果 𝑑𝑖(𝑃) 是第 𝑗 小的,即恰好存在 𝑗−1 个严格比 𝑑𝑖(𝑃) 小的距离,那么就称 𝑃 是一个好点。 小 A 想要知道:所有好点 𝑃 构成的面积是多少?如果不存在好点,那么面积就是 0。你 需要对每一个数对 (𝑖, 𝑗)(1 ≤𝑖, 𝑗≤𝑛)都求出对应的答案。 【输入格式】 从文件 park.in 中读入数据。 输入的第一行包含三个正整数 𝑛, 𝑋, 𝑌,分别表示公园内的路灯数和小 A 能到达的矩形区 域的右上角坐标。 接下来 𝑛 行,每行两个整数 𝑥𝑖, 𝑦𝑖,表示 𝑖 号路灯的坐标。保证所有路灯坐标两两不同。 路灯不一定只在矩形区域外部,有可能在边界上或者内部。 【输出格式】 输出到文件 park.out 中。 输出一个 𝑛 行 𝑛 列的实数矩阵(建议每个实数保留小数点后不超过 10 位,防止输出文件 过大),第 𝑖 行第 𝑗 列表示对应的数对为 (𝑖, 𝑗) 的答案。同一行的两个数中间用一个空格隔开。 选手输出与标准程序输出的相对误差或绝对误差不超过 10−6 即认为选手输出正确。 【样例1 输入】 1 3 1 1 2 ‐1 0 3 0 1 4 1 ‐1 【样例1 输出】 第4 页 共9 页
CCF NOI 2024 四川省代表队评测活动 第一试 公园(park) 1 0.00000000 0.50000000 0.50000000 2 0.93750000 0.06250000 0.00000000 3 0.06250000 0.43750000 0.50000000 【样例1 解释】 样例 1 如图 1 所示。其中区域 1 为梯形 BGHD,区域 2 为多边形 GFJIH,区域 3 为三 角形 JEI,面积分别为 𝑆1 = 1 2,𝑆2 = 7 16,𝑆3 = 1 16。这些区域都不包括边界。 图 1: 样例 1 图示 对于区域 1 中的点 𝑃,满足 𝑑1(𝑃) > 𝑑2(𝑃),𝑑1(𝑃) > 𝑑3(𝑃),𝑑2(𝑃) > 𝑑3(𝑃)。 对于区域 2 中的点 𝑃,满足 𝑑1(𝑃) > 𝑑2(𝑃),𝑑3(𝑃) > 𝑑1(𝑃),𝑑2(𝑃) > 𝑑3(𝑃)。 对于区域 3 中的点 𝑃,满足 𝑑1(𝑃) > 𝑑2(𝑃),𝑑3(𝑃) > 𝑑1(𝑃),𝑑3(𝑃) > 𝑑2(𝑃)。 因此对于第一个点: • 不存在 𝑑1(𝑃) 是第 1 小的区域,因此输出 0。 • 区域 2 和 3 中,𝑑1(𝑃) 是第 2 小的,因此输出 7 16 + 1 16 = 1 2。 • 区域 1 中,𝑑1(𝑃) 是第 3 小的,因此输出 1 2。 第5 页 共9 页
CCF NOI 2024 四川省代表队评测活动 第一试 公园(park) 【样例2 输入】 1 3 2 2 2 ‐2 1 3 2 4 4 4 1 【样例2 输出】 1 1.73958333 0.77083333 1.48958333 2 0.76041667 1.89583333 1.34375000 3 1.50000000 1.33333333 1.16666667 【样例3 输入】 1 3 3 3 2 3 5 3 ‐4 3 4 3 ‐5 【样例3 输出】 1 8.27678571 0.72321429 0.00000000 2 0.72321429 5.84598214 2.43080357 3 0.00000000 2.43080357 6.56919643 【样例4】 见选手目录下的 park/park4.in 与 park/park4.ans。 这个样例满足测试点 1 ∼4 的条件限制。 【样例5】 见选手目录下的 park/park5.in 与 park/park5.ans。 这个样例满足测试点 5 ∼7 的条件限制。 第6 页 共9 页
CCF NOI 2024 四川省代表队评测活动 第一试 公园(park) 【样例6】 见选手目录下的 park/park6.in 与 park/park6.ans。 这个样例满足测试点 8 ∼10 的条件限制。 【样例7】 见选手目录下的 park/park7.in 与 park/park7.ans。 这个样例满足测试点 11 ∼12 的条件限制。 【样例8】 见选手目录下的 park/park8.in 与 park/park8.ans。 这个样例满足测试点 13 ∼14 的条件限制。 【样例9】 见选手目录下的 park/park9.in 与 park/park9.ans。 这个样例满足测试点 15 ∼20 的条件限制。 【数据范围】 对于所有测试数据保证:1 ≤𝑛≤200,𝑋, 𝑌, |𝑥𝑖|, |𝑦𝑖| ≤106。 测试点编号 𝑛≤ 𝑋, 𝑌, |𝑥𝑖|, |𝑦𝑖| ≤ 特殊性质 1 ∼4 12 106 无 5 ∼7 200 A 8 ∼10 B 11 ∼12 50 无 13 ∼14 200 100 15 ∼20 106 特殊性质 A:这 𝑛 个点都在同一圆上。 特殊性质 B:这 𝑛 个点都在同一条直线上。 第7 页 共9 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 1 1
-1 0
0 1
1 -1
0.00000000 0.50000000 0.50000000
0.93750000 0.06250000 0.00000000
0.06250000 0.43750000 0.50000000
样例 2
3 2 2
-2 1
2 4
4 1
1.73958333 0.77083333 1.48958333
0.76041667 1.89583333 1.34375000
1.50000000 1.33333333 1.16666667