|
||||||||||
line symmetricTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 891 Accepted Submission(s): 173 Problem Description You are given a simple polygon in a two-dimensional plane. Please check whether we can move at most one point such that the simple polygon becomes a line-symmetric simple polygon. Note that you cannot reorder these points. If you move the $i$-th point, it still connects to the $(i-1)$-th point and the $(i+1)$-th point in the original order. Also, you cannot move a point to a location having an existing point. Input The first line contains an integer $T$ indicating the number of tests. Each test begins with one line containing one integer $n$, denoting the number of points in the polygon. Then, the $i$-th line in the following $n$ lines contains two integers $x_i, y_i$, $(x_i, y_i)$ is the coordinate of the $i$-th point. For any $1 \le i < n$, the $i$-th point is connected to the $(i+1)$-th point with an edge. Also, the $n$-th point is connected to the first point. * $1 \le T \le 40$ * $3 \le n \le 1000$ * coordinates are in the range $[-1000, 1000]$ Output For each test, if you can move at most one point making the polygon line-symmetric, print a character 'Y' in a line, otherwise print a character 'N' in a line. Please note that the final polygon also has to be a simple polygon. Sample Input
Sample Output
Source | ||||||||||
|