Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

正方形：Square

矩形：Rectangle

菱形：Rhombus

平行四边形：Parallelogram

梯形：Trapezium

普通四边形：Ordinary Quadrilateral

考慮先做一次凸包，以免拉到對角線進行判斷。

接著判斷邊與邊之間的關係。

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct Pt {
    long long x, y;
    bool operator<(const Pt &a) const {
        if(x != a.x)
            return x < a.x;
        return y < a.y;
    }
    Pt operator-(const Pt &a) {
        Pt r;
        r.x = x-a.x, r.y = y-a.y;
        return r;
    }
};
long long cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+4);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
long long dot(Pt a, Pt b) {
    return a.x*b.x + a.y*b.y;
}
long long len(Pt a) {
    return a.x*a.x + a.y*a.y;
}
int main() {
    int testcase, cases = 0;
    int i, j, k;
    Pt D[50], CH[50];
    scanf("%d", &testcase);
    while(testcase--) {
        for(i = 0; i < 4; i++)
            scanf("%lld %lld", &D[i].x, &D[i].y);
        int flag = monotone(4, D, CH);
        Pt a, b, c, d;
        Pt o;
        o.x = o.y = 0;
        a = CH[0], b = CH[1], c = CH[2], d = CH[3];
        printf("Case %d: ", ++cases);
        if(flag != 4) {
            puts("Ordinary Quadrilateral");
            continue;
        }
        if(dot(b-a, d-a) == 0 && dot(c-b, a-b) == 0 && dot(d-c, b-c) == 0) {
            if(len(b-a) == len(c-b))
                puts("Square");
            else
                puts("Rectangle");
        } else if(len(b-a) == len(c-b) && len(b-a) == len(d-c) && len(b-a) == len(a-d))
            puts("Rhombus");
        else if(cross(o, b-a, c-d) == 0 && cross(o, c-b, d-a) == 0)
            puts("Parallelogram");
        else if(cross(o, b-a, c-d) == 0 || cross(o, c-b, d-a) == 0)
            puts("Trapezium");
        else
            puts("Ordinary Quadrilateral");
    }
    return 0;
}