luogu#P10533. [Opoi 2024] 热核武器
[Opoi 2024] 热核武器
题目背景
跳蚤国与蛐蛐国正在激战!
上面是战术核显卡,与题目没有关联。
题目描述
跳蚤国的国土可以看作平面直角坐标系。
跳蚤国有 座城市,有 座是首都,位于 ,另 座是普通城市,在这里假设首都为 号城市,其他城市编号为 至 ,对于每一座普通城市,位于 。
由于跳蚤国财力有限,对于每一个不是首都的城市 ,它会选择一个城市 修建一条双向公路。令 为 , 城市的欧几里得距离,则对于每一个不是首都的城市 ,它所对应的 则是满足 , 的所有点中 最小的点,如有多个合法 ,取其中编号最小的一个。
定义一座城市的 值为这个城市走到首都所需要的最小道路数 ,如果走不到首都,设 值为 。
蛐蛐国要对跳蚤国进行战术核显卡打击,这次行动分为两个组:洛伦兹组和安培组。每个组都要对跳蚤国的部分城市进行打击,其中两个组需要恰好把跳蚤国每个城市打击一遍。
对于这两个组来说,名利是最重要的,而蛐蛐国的评功标准是按照本次行动所打击城市的 值和。所以你需要求出:有没有一种划分方式使得洛伦兹组和安培组分别的打击城市的 值和相等,可以,输出 Yes
,否则输出 No
。
输入格式
第 行输入一个整数 ,表示跳蚤国普通城市的数目。
接下来第 行,第 行输入两个整数,表示第 座城市的横纵坐标 。
输出格式
一行一个字符串,Yes
或者 No
。表示是否会有一种方法使得洛伦兹组和安培组分别的打击城市的 值和相等。
4
-1 -1
1 0
1 -2
-2 2
Yes
提示
样例解释
这幅图是长这样的:
对于 , 和 满足 ,但是 离 距离更近,添加边 。
对于 ,只有 满足 ,添加边 。
对于 ,, 和 满足 ,但是 离 距离最近,因此添加边 。注意这里是因为在 处考虑时,最优点为 ,所以 才向 修建了一条公路,和公路 完全独立。
对于 ,其他所有点都满足 ,但是 离 距离最近,添加边 。
得到下面的表:
城市编号 | 值 |
---|---|
0 | 1 |
1 | 2 |
2 | |
3 | |
4 | 2 |
所以把 分给洛伦兹组, 分给安培组即可。
数据范围
,。
特殊说明
由于本题输出只有 Yes
和 No
,所以本题采用最小分值评测法,即取所有测试点的得分最小值作为结果。