UVa: 1595 - Symmetry

http://blog.csdn.net/crazy__chen/article/details/43544079

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

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

则左边的图形有对称轴，右边没有。

思路1：如点集存在对称轴，则对称轴为点集x坐标和的平均。然后用set存储每个点(输入点不同),遍历每一个点，通过求得的对称轴，计算它的对称点，若不存在则输出“NO”。
思路2：暴力枚举，如果存在对称轴的话那么对称轴的横坐标一定是最左边的点和最右边的点的中点   为了避免中点是小数  可以将横坐标都乘上2  然后在判断所有点是否有对称点就行了

 static HashSet<Point> points = new HashSet<Point>();
 
 public static void main(String[] args) {
  //测试数据
  points.add(new Point(-2, 5));
  points.add(new Point(6, 5));
  points.add(new Point(2, 3));
  points.add(new Point(0, 0));
  points.add(new Point(4, 0));
      
  int sum = 0;
  for(Point point : points){
   sum += point.x;
  }
  sum = sum/points.size();//这个就是对称轴
  
  //检查每个点是否存在对称点
  for(Point point : points){
   if(!points.contains(new Point(sum*2-point.x, point.y))){
    System.out.println("不对称");
    System.exit(0);    
   }
  }
  System.out.println("对称");
 }   

http://blog.csdn.net/acvay/article/details/43015507

没想到暴力枚举可以过  如果存在对称轴的话那么对称轴的横坐标一定是最左边的点和最右边的点的中点   为了避免中点是小数  可以将横坐标都乘上2  然后在判断所有点是否有对称点就行了

bool have(int i)
{
    for(int j = 0; j < n; ++j)
        if(y[i] == y[j] && x[i] + x[j] == 2 * mx) return true;
    return false;
}

int main()
{
    int cas, lx, rx, a, i;
    scanf("%d", &cas);
    while(cas--)
    {
        lx = rx = 0;
        scanf("%d", &n);
        for(i = 0; i < n; ++i)
        {
            scanf("%d%d", &a, &y[i]);
            x[i] = a * 2;
            if(x[i] < x[lx]) lx = i;
            if(x[i] > x[rx]) rx = i;
        }
        mx = (x[lx] + x[rx]) / 2;
        for(i = 0; i < n; ++i)
            if(!have(i)) break;

        if(i >= n) puts("YES");
        else puts("NO");
    }
    return 0;
}

http://m.blog.csdn.net/blog/qq_15096707/43882793
http://www.1point3acres.com/bbs/thread-147293-1-1.html
二问：给一堆点，判断有没有一条line使得这些点关于这条line对称。一上来简直懵逼。。。小哥看我搞不出来，出了个简化版本，给一堆点和一条line，判断这堆点是否关于这条line对称，假设判断关于这条line对称的function是存在的。
写出这个来以后小哥又让我继续写original problem，结果时间就到了。。。
应该可以先计算所有点连成的线的中点，然后依次判断计算两两中点连成的线是不是symmetry line。但是这样复杂度就太高了。