判断是否为轴对称图形
问题描述：按一种顺/逆时针顺序给出平面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;
}