游客 注册 | 登录
中文 | En

1086 - 镜面对称

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

给你一个简单多边形，请你判断这个简单多边形是不是镜面对称的。

例如下图两个简单多边形都是镜面对称的。


<img src="http://tk.hustoj.com:80/attached/image/20130606/20130606220304_18840.png" alt="" />

题目输入

输入包含多组测试数据。
每组输入的第一行是一个整数N（3<=N<=500），表示简单多边形有N个顶点。
接下来N行，每行输入两个整数x和y，表示简单多边形的某个顶点坐标。
顶点坐标保证按照顺时针顺序输入。

题目输出

对于每组输入，如果此简单多边形是镜面对称的则输出“YES”，否则输出“NO”。

输入/输出样例

输入格式

3
-1 0
0 1
1 0

输出格式

YES

C++解答

#include<stdio.h>

int a[501],b[501],n;

bool flg1(int x,int y,int i)
{
	long long da=a[1]-a[i];
	long long db=b[1]-b[i];
	long long ha=a[1]+a[i];
	long long hb=b[1]+b[i];
	return -da*(a[x]+a[y])+hb*db+da*ha-db*(b[x]+b[y])==0;
}

int flg2(int x,int y)
{
	long long da=a[2]-a[n];
	long long db=b[2]-b[n];
	long long ha=a[2]+a[n];
	long long hb=b[2]+b[n];
	return -da*(a[x]+a[y])+hb*db+da*ha-db*(b[x]+b[y])==0;
}

bool judge1(int i)
{
	for(int j=i+1;j<=(n+i+1)/2;j++)
    {
		int x=j,y=n-(j-(i+1));
		if(!flg1(x,y,i))
			return false;
		if((a[y]-a[x])*(b[1]-b[i])!=(a[1]-a[i])*(b[y]-b[x]))
			return false;
	}
	for(int j=2;j<=(i+1)/2;j++)
	{
		int y=j,x=i-(j-1);
		if(!flg1(x,y,i))
			return false;
		if((a[y]-a[x])*(b[1]-b[i])!=(a[1]-a[i])*(b[y]-b[x]))
			return false;
	}
	return true;
}

bool judge2()
{
	if((a[2]-a[1])*(a[2]-a[1])+(b[2]-b[1])*(b[2]-b[1])!=(a[n]-a[1])*(a[n]-a[1])+(b[n]-b[1])*(b[n]-b[1]))
		return false;
	for(int i=3;i<=(n+2)/2;i++)
	{
		int x=i,y=n-(i-2);
		if(!flg2(x,y))
			return false;
		if((a[y]-a[x])*(b[2]-b[n])!=(a[2]-a[n])*(b[y]-b[x]))
			return false;
	}
	return true;
}

int main()
{
	int i;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++)
			scanf("%d%d",&a[i],&b[i]);
		bool f=false;
		for(i=2;i<=n;i++)
			if(judge1(i))
			{
				f=true;
				puts("YES");
				break;
			}
		if(!f)
			puts(judge2()?"YES":"NO");
	}
	return 0;
}
请先登陆