#P10533. [Opoi 2024] 热核武器

[Opoi 2024] 热核武器

题目背景

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

level

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

题目描述

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

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

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

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

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

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

输入格式

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

接下来第 2∼N+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

提示

样例解释

这幅图是长这样的:

对于 C1C1,C0C0 和 C2C2 满足 dis(j,0)≤dis(C1,0)dis(j,0) \le dis(C1,0),但是 C0C0 离 C1C1 距离更近,添加边 (C1,C0)(C1,C0)。

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

对于 C3C3,C0C0,C1C1 和 C2C2 满足 dis(j,0)≤dis(C3,0)dis(j,0) \le dis(C3,0),但是 C2C2 离 C3C3 距离最近,因此添加边 (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),但是 C0C0 离 C4C4 距离最近,添加边 (C4,C0)(C4,C0)。

得到下面的表:

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

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

数据范围

1≤N≤5001 \le N \le 500,−106≤xi,yi≤106-10^6 \le x_i,y_i \le 10^6。

特殊说明

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