syhd142  
日历
<2024年5月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678
统计
  • 随笔 - 23
  • 文章 - 122
  • 评论 - 31
  • 引用 - 0

导航

常用链接

留言簿(2)

随笔档案(23)

文章分类(270)

文章档案(122)

我的豆瓣

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
题意:给你n个点集合S,问你是否存在一个对称点,每个点关于这个对称点可以找到另外一个在集合S中的点。对称点不能属于集合S。
解法:对称点如果存在必然是这个n个点的横纵坐标的平均值,可以证明,然而这是一个必要条件,还需要对每个点进行判断是否存在关于对称点对称的集合S中的点。
#include <stdio.h>

#define N 10005

struct Point
{
    
int x, y;
    Point() {};
    Point(
int _x, int _y)
    {
        x 
= _x, y = _y;
    }
}p[N];

bool solve(Point &ave, int n)
{
    
if((ave.x % n) || (ave.y % n)) return 0;
    ave.x 
/= n, ave.y /= n;
    
for(int i = 0; i < n; i++)
    {
        
int x = 2 * ave.x - p[i].x;
        
int y = 2 * ave.y - p[i].y;
        
bool mk = 0;
        
for(int j = 0; j < n; j++)
        {
            
if(x == p[j].x && y == p[j].y)
            {
                mk 
= 1;
                
break;
            }
        }
        
if(!mk) return 0;
    }
    
return 1;
}

int main()
{
    
int t, n;
    scanf(
"%d"&t);
    
while(t--)
    {
        scanf(
"%d"&n);
        Point ave(
00);
        
for(int i = 0; i < n; i++)
        {
            scanf(
"%d %d"&p[i].x, &p[i].y);
            ave.x 
+= p[i].x, ave.y += p[i].y;
        }
        
if((n == 1|| solve(ave, n)) puts("yes");
        
else puts("no");
    }
    
return 0;
}
posted on 2010-10-01 12:13 Fucker 阅读(331) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC简单

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © Fucker Powered by: 博客园 模板提供:沪江博客