计算几何(判断四边形形状) - Determine the Shape - UVA 11800
题意：
给 定 四 个 点 坐 标 ， 判 断 四 边 形 形 状 。 给定四个点坐标，判断四边形形状。给定四个点坐标，判断四边形形状。
输入：
T 组 测 试 数 据 ， T组测试数据，T组测试数据，
每 组 包 括 四 个 点 的 坐 标 。 每组包括四个点的坐标。每组包括四个点的坐标。
输出：
四 边 形 形 状 。 四边形形状。四边形形状。
Sample Input
6
0 0
2 0
2 2
0 2
0 0
3 0
3 2
0 2
0 0
8 4
5 0
3 4
0 0
2 0
3 2
1 2
0 0
5 0
4 3
1 3
0 0
5 0
4 3
1 4
Sample Output
Case 1: Square Case 2: Rectangle Case 3: Rhombus Case 4: Parallelogram Case 5: Trapezium Case 6: Ordinary Quadrilateral
代码：
include<iostream> include<cmath> include<cstdio> include<vector> include<algorithm>
using namespace std; const double eps=1e-10; const double pi=acos(-1.0); struct Point { double x,y; Point(double x=0,double y=0) : x(x), y(y) {} }; //点与向量
typedef Point Vector; Vector operator + (Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y); } Vector operator - (Point A,Point B) { return Vector(A.x-B.x,A.y-B.y); } Vector operator * (Vector A,double p) { return Vector(A.x*p,A.y*p); } Vector operator / (Vector A,double p) { return Vector(A.x/p,A.y/p); } bool operator < (const Point &a,const Point &b) { return a.x<b.x || (a.x==b.x && a.y<b.y); } int dcmp(double x) { if(fabs(x)<eps) return 0; else return x<0 ? -1 : 1; } bool operator == (const Point &a, const Point &b) { return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0; } double Dot(Vector A,Vector B) { return A.x*B.x + A.y*B.y; } double Length(Vector A) { return sqrt(Dot(A,A)); } double Angle(Vector A, Vector B) { return acos(Dot(A,B) / Length(A) / Length(B)); } //A和B夹角
double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; } //若A到B逆时针则为正，否则为负
double Area2(Point A,Point B,Point C) { return Cross(B-A,C-A); } //三角形ABC的面积的两倍(有方向) //点和直线
struct Line {//直线定义
Point v, p; Vector dir; double ang; Line() //构造函数
Line(const Line& L): p(L.p), dir(L.dir), ang(L.ang) { } Line(Point v, Point p):v(v), p(p){ dir=p-v; ang=atan2(dir.y,dir.x); } bool operator < (const Line& L) const //极角排序
{ return ang < L.ang; } Point point(double t) {//返回点P = v + (p - v)*t
return v + dir*t; } }; typedef vector<Point> Polygon; //平行四边形的判定（保证四边形顶点按顺序给出）
bool isParallelogram(Polygon p) { if (dcmp(Length(p[0]-p[1]) - Length(p[2]-p[3])) || dcmp(Length(p[0]-p[3]) - Length(p[2]-p[1]))) return false; Line a = Line(p[0], p[1]); Line b = Line(p[1], p[2]); Line c = Line(p[3], p[2]); Line d = Line(p[0], p[3]); return dcmp(a.ang - c.ang) == 0 && dcmp(b.ang - d.ang) == 0; } //梯形的判定
bool isTrapezium(Polygon p) { Line a = Line(p[0], p[1]); Line b = Line(p[1], p[2]); Line c = Line(p[3], p[2]); Line d = Line(p[0], p[3]); return (dcmp(a.ang - c.ang) == 0 && dcmp(b.ang - d.ang)) || (dcmp(a.ang - c.ang) && dcmp(b.ang - d.ang) == 0); } //菱形的判定
bool isRhombus(Polygon p) { if (!isParallelogram(p)) return false; return dcmp(Length(p[1]-p[0]) - Length(p[2]-p[1])) == 0; } //矩形的判定
bool isRectangle(Polygon p) { if (!isParallelogram(p)) return false; return dcmp(Length(p[2]-p[0]) - Length(p[3]-p[1])) == 0; } //正方形的判定
bool isSquare(Polygon p) { return isRectangle(p) && isRhombus(p); } int check(Polygon p) { if(isSquare(p)) return 1; else if(isRectangle(p)) return 2; else if(isRhombus(p)) return 3; else if(isParallelogram(p)) return 4; else if(isTrapezium(p)) return 5; else return 6; } int main() { int T; scanf("%d",&T); for(int C=1;C<=T;C++) { Polygon p; Point tmp; for(int i=0;i<4;i++) {scanf("%lf%lf",&tmp.x,&tmp.y); p.push_back(tmp);} int t=check(p);//V[0],V[1],V[2],V[3];
swap(p[1],p[2]); t=min(t,check(p));//V[0],V[2],V[1],V[3];
swap(p[1],p[2]); swap(p[2],p[3]); t=min(t,check(p));//V[0],V[1],V[3],V[2];
printf("Case %d: ",C); if(t==1) puts("Square"); else if(t==2) puts("Rectangle"); else if(t==3) puts("Rhombus"); else if(t==4) puts("Parallelogram"); else if(t==5) puts("Trapezium"); else puts("Ordinary Quadrilateral"); } return 0; }
原文创作：希望每天涨粉
原文链接：https://www.cnblogs.com/BlairGrowing/p/13926424.html
