| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 21 | 15 | 8 | 88.889% |
Stefan, David and Felix are preparing an ACM-style programming contest. Stefan proposes the following task:
Given $N$ points on a plane and $N$ movement vectors, find a one-to-one correspondence between vectors and points such that, if one moves (translates) each point by the corresponding vector, the distance between every pair of points will not decrease.
David managed to solve this problem pretty fast and claims it's too easy to be included in the problemset. To convince him, Felix proposed the following update: among all possible solutions, choose the one that maximizes the sum of squares of all resulting pairwise distances.
David still finds the problem to be easy, do you agree?
The first line of the input contains a single integer $N,ドル the number of points and vectors (1ドル \leq N \leq 500$).
Next $N$ lines describe points. Each of them contains two integers $px_i$ and $py_i$ (0ドル \leq |px_i|, |py_i| \leq 10,000円$).
Then follow $N$ lines with vectors descriptions. Each vector is defined by two integers $vx_i$ and $vy_i$ (0ドル \leq |vx_i|, |vy_i| \leq 10,000円$).
If there exists a way to establish a one-to-one correspondence such that all pairwise distances will not decrease, print "Yes" on the first line of the output. On the next line, print $N$ distinct integers from 1ドル$ to $N,ドル $i$-th of these numbers being the vector assigned to $i$-th point.
Do not forget to choose the answer with maximum possible sum of squares of all resulting pairwise distances. If there are still multiple answers, output any of them.
If there is no way to meet the desired requirement, print "No" on the single line of the output.
2 0 0 1 0 2 0 -2 0
Yes 2 1
2 2 2 2 2 -1 -1 -1 -1
Yes 1 2
3 -2 -3 3 1 -3 -3 -3 5 -2 -4 4 -1
Yes 2 3 1
In the first example, there are only two possible ways to establish a one-to-one correspondence between points and vectors. In both correspondences, "1 2" and "2 1", the distance between every pair of points does not decrease. In the first case the sum of squares of all resulting pairwise distances is equal to 9ドル,ドル but in the second one it is equal to 25ドル$. So, the only correct answer is "2 1".
In the second example, there are again only two possible ways to establish a correspondence. In both cases, the distance between every pair of points does not decrease, and the sum of squares of all resulting pairwise distances is equal to 0ドル$. So, both of the answers are correct.