题解 UVA11800 【Determine the Shape】

throusea · 2018-10-31 15:17:06 · 题解

计算几何的入门题。

大家应该学过了平行四边形了吧。（默认已经会二维计算几何了）

判定方法如下：

1. 平行四边形： 对角线互相平分或者用定义。

2. 梯形： 有一组对边平行，一组对边不平行。

   在已知平行四边形的情况下

3. 矩形： 对角线长度相等或用定义。

4. 菱形： 对角线互相垂直（数量积为0）或用定义。

5. 正方形： 即是矩形又是菱形。

题目只是给你几个点的坐标，并不知道那些点能组成对角线。所以枚举组合加上两线段是否相交的判定即可。

找到那两条对角线后，就可以随便乱搞用上面的判定了。

我用的主要是对角线的判定。坐标虽然只有（-10000～10000），但WA的经历告诉我要开long long.

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define LL long long
using namespace std;
struct Point {
    int x,y;
    Point(int x=0,int y=0) : x(x),y(y) { }
};

typedef Point Vector;

Point p[5];
int a[5];
string s[] = {"Ordinary Quadrilateral","Trapezium","Parallelogram","Rhombus","Rectangle","Square"};

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

bool operator == (Point A,Point B) {
    return A.x == B.x && A.y == B.y;
}

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

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

LL dis(Point A,Point B) {
    return (LL)(A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}

bool intersection(Point a1,Point a2,Point b1,Point b2) {
    LL c1 = Cross(a1-a2,b1-a2),c2 = Cross(a1-a2,b2-a2),
        c3 = Cross(b1-b2,a1-b2),c4 = Cross(b1-b2,a2-b2);
    return (LL)c1 * c2 < 0 && c3 * c4 < 0;
}

bool para(Vector A,Vector B) {
    return A.x * B.y == A.y * B.x;
}

int main() {
    int T,Case = 0;
    scanf("%d",&T);
    while(T--) {
        int shape;
        for(int i = 1; i <= 4; i++)
        scanf("%d%d",&p[i].x,&p[i].y);
        if(intersection(p[1],p[2],p[3],p[4])) {
            a[1] = 1; a[2] = 2; a[3] = 3; a[4] = 4;
        }
        if(intersection(p[1],p[3],p[2],p[4])) {
            a[1] = 1; a[2] = 3; a[3] = 2; a[4] = 4;
        }
        if(intersection(p[1],p[4],p[2],p[3])) {
            a[1] = 1; a[2] = 4; a[3] = 2; a[4] = 3;
        }
        // 对角线
        if(p[a[1]] + p[a[2]] == p[a[3]] + p[a[4]]) {
            shape = 2;
            if(Dot(p[a[2]]-p[a[1]],p[a[4]]-p[a[3]]) == 0)
            shape = 3;
            if(dis(p[a[1]],p[a[2]]) == dis(p[a[3]],p[a[4]]))
            if(shape == 3) 
              shape = 5;
            else shape = 4;
            // 平行四边形部分
        }else {
            if(para(p[a[1]]-p[a[3]],p[a[2]]-p[a[4]]) || para(p[a[1]]-p[a[4]],p[a[2]]-p[a[3]]))
              shape = 1;
            else shape = 0;
            // 非平行四边形
        }
        printf("Case %d: ",++Case);
        cout<<s[shape]<<endl;
    }
    return 0;
}