#P10533. [Opoi 2024] 热核武器

    ID: 9770 Type: RemoteJudge 1000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 3 Uploaded By: Tags>动态规划,dp搜索贪心O2优化

[Opoi 2024] 热核武器

题目背景

跳蚤国与蛐蛐国正在激战!

level

上面是战术核显卡,与题目没有关联。

题目描述

跳蚤国的国土可以看作平面直角坐标系。

跳蚤国有 N+1N+1 座城市,有 11 座是首都,位于 (0,0)(0,0),另 NN 座是普通城市,在这里假设首都为 00 号城市,其他城市编号为 11NN,对于每一座普通城市,位于 (xi,yi)(x_i,y_i)

由于跳蚤国财力有限,对于每一个不是首都的城市 ii,它会选择一个城市 jj 修建一条双向公路。令 dis(x,y)dis(x,y)xxyy 城市的欧几里得距离,则对于每一个不是首都的城市 ii,它所对应的 jj 则是满足 dis(j,0)dis(i,0)dis(j,0) \le dis(i,0)jij \ne i 的所有点中 dis(i,j)dis(i,j) 最小的点,如有多个合法 jj,取其中编号最小的一个。

定义一座城市的 γ\gamma 值为这个城市走到首都所需要的最小道路数 +1+1如果走不到首都,设 γ\gamma 值为 00

蛐蛐国要对跳蚤国进行战术核显卡打击,这次行动分为两个组:洛伦兹组和安培组。每个组都要对跳蚤国的部分城市进行打击,其中两个组需要恰好把跳蚤国每个城市打击一遍。

对于这两个组来说,名利是最重要的,而蛐蛐国的评功标准是按照本次行动所打击城市的 γ\gamma 值和。所以你需要求出:有没有一种划分方式使得洛伦兹组和安培组分别的打击城市的 γ\gamma 值和相等,可以,输出 Yes,否则输出 No

输入格式

11 行输入一个整数 NN,表示跳蚤国普通城市的数目。

接下来第 2N+12 \sim N+1 行,第 i+1i+1 行输入两个整数,表示第 ii 座城市的横纵坐标 (xi,yi)(x_i,y_i)

输出格式

一行一个字符串,Yes 或者 No。表示是否会有一种方法使得洛伦兹组和安培组分别的打击城市的 γ\gamma 值和相等。

4
-1 -1
1 0
1 -2
-2 2
Yes

提示

样例解释

这幅图是长这样的:

对于 C1C1C0C0C2C2 满足 dis(j,0)dis(C1,0)dis(j,0) \le dis(C1,0),但是 C0C0C1C1 距离更近,添加边 (C1,C0)(C1,C0)

对于 C2C2,只有 C0C0 满足 dis(j,0)dis(C2,0)dis(j,0) \le dis(C2,0),添加边 (C2,C0)(C2,C0)

对于 C3C3C0C0C1C1C2C2 满足 dis(j,0)dis(C3,0)dis(j,0) \le dis(C3,0),但是 C2C2C3C3 距离最近,因此添加边 (C3,C2)(C3,C2)注意这里是因为在 C3C3 处考虑时,最优点为 C2C2,所以 C3C3 才向 C2C2 修建了一条公路,和公路 (C2,C0)(C2,C0) 完全独立。

对于 C4C4,其他所有点都满足 dis(j,0)dis(C4,0)dis(j,0) \le dis(C4,0),但是 C0C0C4C4 距离最近,添加边 (C4,C0)(C4,C0)

得到下面的表:

城市编号 γ\gamma
0 1
1 2
2
3
4 2

所以把 0,1,20,1,2 分给洛伦兹组,3,43,4 分给安培组即可。

数据范围

1N5001 \le N \le 500106xi,yi106-10^6 \le x_i,y_i \le 10^6

特殊说明

由于本题输出只有 YesNo,所以本题采用最小分值评测法,即取所有测试点的得分最小值作为结果。