UVA 11800 - Determine the Shape 几何

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2900

题目大意：

给定平面上的4个点，没有3点共线，你的任务是判断着4个点能组成什么样的四边形。（正方形，矩形，菱形，平行四边形，菱形，梯形，普通四边形）

思路：

从后面开始判断，梯形一组平行边即可。

平行四边形要两组，而菱形对角线垂直，矩形有一个角为直角，正方形既是矩形又是菱形。

至于判断平行和垂直，用叉乘和点乘即可。

要注意的是，不一定是按照边a,b,c,d这样的顺序，看图就知道了

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int MAXN=300+10;

struct Point

{

	double x, y;

	Point(double x=0, double y=0):x(x),y(y) { }

};

typedef Point Vector;

Vector operator + (const Vector& A, const Vector& B) { return Vector(A.x+B.x, A.y+B.y); }

Vector operator - (const Point& A, const Point& B) { return Vector(A.x-B.x, A.y-B.y); }

Vector operator * (const Vector& A, double p) { return Vector(A.x*p, A.y*p); }

double Dot(const Vector& A, const Vector& B) { return A.x*B.x + A.y*B.y; }

double Cross(const Vector& A, const Vector& B) { return A.x*B.y - A.y*B.x; }

Point a,b,c,d;

void print(int ans)

{

	switch (ans)

	{

	case 0:puts("Ordinary Quadrilateral");break;

	case 1:puts("Trapezium");break;

	case 2:puts("Parallelogram");break;

	case 3:puts("Rhombus");break;

	case 4:puts("Rectangle");break;

	case 5:puts("Square");break;

	}

}

int solve(const Point &a,const Point &b,const Point &c,const Point &d)

{

	int ans=0;

	Vector ab=b-a,bc=c-b,cd=d-c,da=a-d;

	if(Cross(ab,cd)==0||Cross(da,bc)==0) //梯形

		ans=1;

	if(Cross(ab,cd)==0&&Cross(da,bc)==0) //平行四边形

	{

		ans=2;

		if(Dot(c-a,b-d)==0)         //菱形

			ans=3;

		if(Dot(ab,bc)==0)      //矩形

			ans=4;

		if(Dot(c-a,b-d)==0 && Dot(ab,bc)==0) //正方形

			ans=5;

	}

	return ans;

}

int main()

{

	int T,kase=1;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y);

		int ans=0;

		ans=solve(a,b,c,d);

		ans=max(ans,solve(a,c,b,d));

		ans=max(ans,solve(a,b,d,c));

		printf("Case %d: ",kase++);

		print(ans);

	}

	return 0;

}