A10145. Wilbur and Points
编程题
普及/提高-
知识点
题目描述
The first line of the input consists of a single integer $n$ ( $1<=n<=100000$ ) — the number of points in the set Wilbur is playing with.
Next follow $n$ lines with points descriptions. Each line contains two integers $x$ and $y$ ( $0<=x,y<=100000$ ), that give one point in Wilbur's set. It's guaranteed that all points are distinct. Also, it is guaranteed that if some point ( $x$ , $y$ ) is present in the input, then all points ( $x'$ , $y'$ ), such that $0<=x'<=x$ and $0<=y'<=y$ , are also present in the input.
The last line of the input contains $n$ integers. The $i$ -th of them is $w_{i}$ ( $-100000<=w_{i}<=100000$ ) — the required special value of the point that gets number $i$ in any aesthetically pleasing numbering.
Next follow $n$ lines with points descriptions. Each line contains two integers $x$ and $y$ ( $0<=x,y<=100000$ ), that give one point in Wilbur's set. It's guaranteed that all points are distinct. Also, it is guaranteed that if some point ( $x$ , $y$ ) is present in the input, then all points ( $x'$ , $y'$ ), such that $0<=x'<=x$ and $0<=y'<=y$ , are also present in the input.
The last line of the input contains $n$ integers. The $i$ -th of them is $w_{i}$ ( $-100000<=w_{i}<=100000$ ) — the required special value of the point that gets number $i$ in any aesthetically pleasing numbering.
输入格式
If there exists an aesthetically pleasant numbering of points in the set, such that $s(x_{i},y_{i})=y_{i}-x_{i}=w_{i}$ , then print "YES" on the first line of the output. Otherwise, print "NO".
If a solution exists, proceed output with $n$ lines. On the $i$ -th of these lines print the point of the set that gets number $i$ . If there are multiple solutions, print any of them.
If a solution exists, proceed output with $n$ lines. On the $i$ -th of these lines print the point of the set that gets number $i$ . If there are multiple solutions, print any of them.
输出格式
In the first sample, point ( $2$ , $0$ ) gets number $3$ , point ( $0$ , $0$ ) gets number one, point ( $1$ , $0$ ) gets number $2$ , point ( $1$ , $1$ ) gets number $5$ and point ( $0$ , $1$ ) gets number $4$ . One can easily check that this numbering is aesthetically pleasing and $y_{i}-x_{i}=w_{i}$ .
In the second sample, the special values of the points in the set are $0$ , $-1$ , and $-2$ while the sequence that the friend gives to Wilbur is $0$ , $1$ , $2$ . Therefore, the answer does not exist.
In the second sample, the special values of the points in the set are $0$ , $-1$ , and $-2$ while the sequence that the friend gives to Wilbur is $0$ , $1$ , $2$ . Therefore, the answer does not exist.
输入输出样例
输入 #1
5 2 0 0 0 1 0 1 1 0 1 0 -1 -2 1 0
输出 #1
YES 0 0 1 0 2 0 0 1 1 1
输入 #2
3 1 0 0 0 2 0 0 1 2
输出 #2
NO
说明/提示
In the first sample, point ( $2$ , $0$ ) gets number $3$ , point ( $0$ , $0$ ) gets number one, point ( $1$ , $0$ ) gets number $2$ , point ( $1$ , $1$ ) gets number $5$ and point ( $0$ , $1$ ) gets number $4$ . One can easily check that this numbering is aesthetically pleasing and $y_{i}-x_{i}=w_{i}$ .
In the second sample, the special values of the points in the set are $0$ , $-1$ , and $-2$ while the sequence that the friend gives to Wilbur is $0$ , $1$ , $2$ . Therefore, the answer does not exist.
In the second sample, the special values of the points in the set are $0$ , $-1$ , and $-2$ while the sequence that the friend gives to Wilbur is $0$ , $1$ , $2$ . Therefore, the answer does not exist.