欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-02 18:57:21
...

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


分析:

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

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

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

我 们 先 选 出 a 边 , 然 后 从 剩 下 的 3 条 边 中 , 选 择 2 条 边 作 为 a 的 邻 边 , 共 有 C 3 2 = 3 种 可 能 : 我们先选出a边,然后从剩下的3条边中,选择2条边作为a的邻边,共有C_3^2=3种可能: a32aC32=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,da,c,b,da,b,d,c

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

代码:

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