QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 8360. distance

统计

这是唯一一道没有题目背景的题。

Z 有一个二维平面,这个二维平面上有 $n$ 个点,第 $i$ 个点的坐标为 $(x_i,y_i)$。

Z 想要移动这些点。小 Z 有 $n$ 种移动方式,第 $i$ 种方式可以看成一个向量 $(u_i,v_i)$,将第 $i$ 种移动方式作用到第 $j$ 个点上,第 $j$ 个点的坐标会变为 $(x_j+u_i,y_j+v_i)$。

Z 会对每个点正好作用一种移动方式,且每种移动方式正好使用一次。这相当于找到一个 $n$ 阶排列 $p$,并对第 $i$ 个点作用第 $p_i$ 种移动方式。

Z 对这些点之间的距离很感兴趣。小 Z 更喜欢远的距离,因此小 Z 希望在移动后,任意两个点之间的距离不会变小。这里两个点 $(x_1,y_1),(x_2,y_2)$ 的距离定义为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。

Z 希望知道是否存在满足要求的操作方式。如果存在这样的方式,在满足要求的基础上,小 Z 希望最大化每个点对的距离的平方和,你需要求出一个这样的方式。但如果你的方式只满足了要求而没有最大化距离的平方和,你也可以获得一半的分数。

输入格式

输入文件第一行包含一个正整数 $n$,表示点的数量。

接下来 $n$ 行,每行两个整数 $x_i,y_i$,依次表示所有点的坐标。

接下来 $n$ 行,每行两个整数 $u_i,v_i$,依次表示所有向量的坐标。

输出格式

如果不存在满足要求的方式,则输出一行一个字符串 No

否则,首先输出一行一个字符串 Yes,接下来一行输出一个 $n$ 阶排列 $p_1,\cdots,p_n$,表示你找到的方案。

注意 spj 对大小写敏感。

样例

样例输入 #1

2
1 1
-1 -1
-1 -1
1 1

样例输出 #1

Yes
2 1

注意这里 $(1,2)$ 不是一组合法的解,因为按照 $(1,2)$ 方式操作后,两个点重合,距离变小。

样例输入 #2

5
1 1
4 5
1 4
1 9
1 9
8 1
1 9
2 6
0 8
1 7

样例输出 #2

Yes
1 3 5 2 4

这只是一种可能的输出,还有其它的最优解,例如 $(1,3,5,4,2)$。

注意点可以重叠。(以及向量可以为零向量)

数据范围与限制

对于所有数据,$n\leq 500,|x_i|,|y_i|,|u_i|,|v_i|\leq 10^4$。

如果你对于所有数据正确判断了是否有解,且对于有解的数据输出了满足条件的方案,则你可以获得 $50\%$ 的分数。

在此基础上,如果对于每组数据你输出的方案得到的距离平方和是所有合法方案中距离平方和最大的,则你可以获得所有分数。

子任务编号 子任务分数 特殊限制
$1$ $20$ $n\leq 10$
$2$ $10$ $n\leq 20$
$3$ $20$ $n\leq 50$
$4$ $34$ $n\leq 150$
$5$ $16$ 无特殊限制