判断是否为轴对称图形

判断是否为轴对称图形

问题描述:按一种顺/逆时针顺序给出平面N个点的坐标,判断这N个点所形成的图形是否轴对称。为了简化题目,本题两点所构成的线段均平行于坐标轴

题目链接:https://vjudge.net/problem/FZU-2035

目前的想法是将所有的点都保存到vector中,取第[i]个和第[i+N/2]个点连线,然后取遍所有j可能的检查[i+j]和[i-j]这两个点的中点是否在第[i]和第[i+N/2]点的连线上,如果是轴对称图形的话,那么一定存在一条对角的连线,使得所有其它点关于这条连线对称。

但是编写了程序提交总是通不过,可能数据不够强。现在的程序考虑了可能出现数据中的点不是多边形顶点的情况,例如(0,0),(1,0),(3,0)的情况已经进行了处理。

用C++编写了Point和Line类,主要用于维护对于点与直线的位置关系以及运算。如果万一有哪个公式出了小差错,就会无法通过,这也不知道是思路有问题还是某函数的哪部分出错。有机会再细查查。

现在使用的一组测试数据:

3
4
0 0
0 1
1 1
1 0
6
0 0
4 0
4 2
1 2
1 4
0 4
11
4 0
4 3
5 3
5 5
3 5
3 4
0 4
0 0
1 0
2 0
3 0

程序如下

#include <cstdio>
#include <vector>
using std::vector;
#include <cmath>

int __NaN=0xFFC00000;
const float NaN=*((float *)&__NaN);

int gcd(int x,int y)
{
	if(x%y==0)
	{
		return y;
	}	
	else
	{
		return gcd(y,x%y);
	}
}

class Point{
	private:
		double X,Y;
		bool valid;
	public:
		Point(){}
		Point(bool v)
		{
			valid = v;
		}
		Point(double x,double y)
		{
			X=x;Y=y;
			valid=true;
		}
		bool isValid()
		{return valid;}

		double getX()
		{
			if(valid)
				return X;
			else
				return NaN;
		}

		double getY()
		{
			if(valid)
				return Y;
			else
				return NaN;
		}
		Point midPoint(Point p);
};

Point Point::midPoint(Point p)
{
	if(valid && p.isValid())
		return Point((X+p.getX())/2,(Y+p.getY())/2);
	else
		return Point(false);
}


class Line{
	private:
		double A,B,C;
	public:
		Line(){}
		Line(double a,double b,double c)
		{
			A=a;
			B=b;
			C=c;
		}
		Line(Point a,Point b)
		{
			double dx = a.getX()-b.getX();
			double dy = a.getY()-b.getY();
			A=dy;
			B=-1.0*dx;
			C=dx*a.getY()-dy*a.getX();
		}
		void output()
		{
			printf("%.1fx%+.1fy%+.1f=0\n",A,B,C);
		}

		double dist(Point a);
		Point CrossPoint(Line b);
		bool inLine(Point p);
};


double Line::dist(Point a)
{
	return (A*a.getX()+B*a.getY()+C)/sqrt(A*A+B*B);
}

Point Line::CrossPoint(Line L)
{
	double tx,ty;
	if(A*L.A*B*L.B ==0)
	{
		if((A==0 && L.A==0) || (B==0 && L.B==0))
		{
			return Point(false);
		}
		else
		{
			if(A==0)
			{
				ty = -1*C/B;
				tx = -1*(L.B*ty+L.C)/L.A;
			}
			else if(L.A==0)
			{
				ty = -1*L.C/L.B;
				tx= -1*(B*ty+C)/A;
			}
			else if(B==0)
			{
				tx = -1*C/A;
				ty = -1*(L.C+L.A*tx)/L.B;
			}
			else //L.B==0
			{
				tx = -1*L.C/L.A;
				ty = -1*(C+A*tx)/B;
			}
			return Point(tx,ty);
		}
	}
	else if((A-L.A)*(B-L.B)==0)
	{
		// assume there no 2 same lines;
		if(A-L.A==0)
		{
			ty=(C-L.C)/(L.B-B);
			tx = -1*(B*ty+C)/A;
		}
		else  // B-L.B==0
		{
			tx = (C-L.C)/(L.A-A);
			ty = -1*(C+A*tx)/B;
		}
		return Point(tx,ty);
	}
	else
	{
		double D=L.A*B-A*L.B, D1 = L.A*C+A*L.C;
		ty = -D1/D; // assume there no parallel lines
		tx = -1*(B*ty+C)/A;
		return Point(tx,ty);
	}
}

bool Line::inLine(Point p)
{
	const double epsilon = 0.00000001;
	return fabs(A*p.getX()+B*p.getY()+C)<epsilon;
}

void solve()
{
	vector<Point> v;
	int i,N,x,y;
	scanf("%d",&N);
	for(i=0;i<N;i++)
	{
		scanf("%d%d",&x,&y);
		v.push_back(Point(x,y));		
	}
	for(i=0;i<N+2;i++)
	{
		Line L0 = Line(v[i%v.size()],v[(i+2)%v.size()]);
		if(L0.inLine(v[(i+1)%v.size()]))
		{
			v.erase(v.begin()+(i+1)%v.size());
			i-=1;
		}
	}

	int RealPoints = v.size();

	int winFlag = 0;
	for(i=0;i<RealPoints/2 && winFlag==0;i++)
	{
		winFlag=1;
		Line L0 = Line(v[i],v[i+RealPoints/2]);

		for(int j=1;j<RealPoints/2 && winFlag==1;j++)
		{
			Point r = v[(i+j)%RealPoints].midPoint(v[(i+RealPoints-j)%RealPoints]);
			if(L0.inLine(r)==false)
			{
				winFlag = 0;
				break;
			}
		}
		if(winFlag==1)
		{
			break;
		}
	}

	if(winFlag==1)
		printf("YES\n");
	else
		printf("NO\n");
	return ;
}

int main(void)
{
	int T;
	scanf("%d",&T);
	for(int i = 0 ;i<T;i++)
	{
		printf("Case %d: ",i+1);
		solve();
	}

	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注