对称轴(Symmetry)

Symmetry

Time limit: 3.000 seconds

The figure shown on the left is left-right symmetric as it is possible to fold the sheet of paper along a vertical line, drawn as a dashed line, and to cut the figure into two identical halves. The figure on the right is not left-right symmetric as it is impossible to find such a vertical line.

Write a program that determines whether a figure, drawn with dots, is left-right symmetric or not. The dots are all distinct.

Input

The input consists of T test cases. The number of test cases T is given in the first line of the input file. The first line of each test case contains an integer N , where N (1N1, 000) is the number of dots in a figure. Each of the following N lines contains the x-coordinate and y-coordinate of a dot. Both x-coordinatesand y-coordinates are integers between -10,000 and 10,000, both inclusive.

Output

Print exactly one line for each test case. The line should contain `YES' if the figure is left-right symmetric. and `NO', otherwise.

The following shows sample input and output for three test cases.

Sample Input

3                                            5                                            
-2 5                                         
0 0 
6 5 
4 0 
2 3 
4 
2 3 
0 4 
4 0 
0 0 
4 
5 14 
6 10
5 10 
6 14

Sample Output

YES NO 
YES

【题目】

       给出平面上N（N<=1000）个点，问是否可以找到一条竖线，使得所有点左右对称。

【分析】

       先找到可能存在的对称轴的位置——最左的横坐标与最右的横坐标的和除以2，在这里，由于可能出现不整除的情况，所以我们先不对它俩的和除以2，在后续中我们只要注意它还没除以2即可。找出这个可能的位置后，我们进行枚举，由其中一个点根据对称轴去寻找它的对称点，如果该对称点不存在，则说明没有一条竖线使得这些点对称。只有当所有点都能根据这条对称轴寻找它们所属的对称点，才能说明该条对称轴存在。

用java语言编写程序，代码如下：

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    int t = input.nextInt();

    for(int i = 0; i < t; i++) {
      int n = input.nextInt();
      
      int lx = 10001;
      int rx = -10001;
      int[][] c = new int[n][2];
      for(int j = 0; j < n; j++) {
        c[j][0] = input.nextInt();
        c[j][1] = input.nextInt();
        
        if(c[j][0] < lx) lx = c[j][0];
        if(c[j][0] > rx) rx = c[j][0];
      }
      //System.out.println(lx + "....." + rx);
      int symmetry = lx + rx;
      
      if(handle(symmetry, c))
        System.out.println("YES");
      else
        System.out.println("NO");
    }
  }
  
  public static boolean handle(int sym, int[][] c) {
    for(int i = 0; i < c.length; i++) {
      int j;
      for(j = 0; j < c.length; j++) {
        if(c[i][1] == c[j][1] && sym == c[i][0] + c[j][0])
          break;
      }
      
      if(j == c.length)
        return false;
    }
    return true;
  }
}