计算几何(判断四边形形状) - Determine the Shape - UVA 11800

计算几何(判断四边形形状) - 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

说明：

• Square: All sides are of equal size all angles are 90◦
• Rectangle: Opposite sides are of equal size and all angles are 90◦
• Rhombus: All sides are of equal size but no angle is 90◦
• Parallelogram: Opposite sides are of equal size but no angle is 90◦
• Trapezium: Any two opposite sides are parallel but the other two is not.
• Simple Polygon: Polygon having no self intersecting edge.

按 照 上 述 顺 序 依 次 判 断 四 边 形 的 类 型 。 按照上述顺序依次判断四边形的类型。 按照上述顺序依次判断四边形的类型。

若 不 是 前 五 种 类 型 ， 则 输 出 ′ ′ O r d i n a r y   Q u a d r i l a t e r a l ′ ′ ， 否 则 ， 对 应 输 出 四 边 形 的 形 状 。 若不是前五种类型，则输出''Ordinary \ Quadrilateral''，否则，对应输出四边形的形状。 若不是前五种类型，则输出′′Ordinary Quadrilateral′′，否则，对应输出四边形的形状。

数据范围：

T ≤ 50000 , − 10000 ≤ x i , y i ≤ 10000 T ≤ 50000,−10000 ≤ x_i, y_i ≤ 10000 T≤50000,−10000≤xi​,yi​≤10000

---

分析：

由 于 输 入 的 四 个 点 不 是 按 照 四 边 形 的 逆 时 针 / 顺 时 针 的 顺 序 给 出 的 ， 由于输入的四个点不是按照四边形的逆时针/顺时针的顺序给出的， 由于输入的四个点不是按照四边形的逆时针/顺时针的顺序给出的，

所 以 ， 判 断 的 时 候 需 要 考 虑 顺 序 问 题 。 所以，判断的时候需要考虑顺序问题。 所以，判断的时候需要考虑顺序问题。

四 个 点 A , B , C , D 构 成 四 边 形 共 有 4 条 边 a , b , c , d ， 四个点A,B,C,D构成四边形共有4条边a,b,c,d， 四个点A,B,C,D构成四边形共有4条边a,b,c,d，

我 们 先 选 出 a 边 ， 然 后 从 剩 下 的 3 条 边 中 ， 选 择 2 条 边 作 为 a 的 邻 边 ， 共 有 C 3 2 = 3 种 可 能 ： 我们先选出a边，然后从剩下的3条边中，选择2条边作为a的邻边，共有C_3^2=3种可能： 我们先选出a边，然后从剩下的3条边中，选择2条边作为a的邻边，共有C32​=3种可能：

按 照 某 个 时 针 顺 序 分 别 是 ： a , b , c , d 、 a , c , b , d 、 a , b , d , c 按照某个时针顺序分别是：a,b,c,d、a,c,b,d、a,b,d,c 按照某个时针顺序分别是：a,b,c,d、a,c,b,d、a,b,d,c

故 对 于 A , B , C , D 四 个 顶 点 ， 可 能 构 成 3 种 不 同 的 四 边 形 。 故对于A,B,C,D四个顶点，可能构成3种不同的四边形。 故对于A,B,C,D四个顶点，可能构成3种不同的四边形。

代码：

#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;
}