這道題比較基礎，方法也比較多，我的話是使用了向量法進行計算。
任意枚舉3個點，看這3個點確定的3個向量和第四個點是否構成一個平行四邊形，如果是平行四邊形，再進行特殊圖形的判斷。
14118653
11800
Determine the Shape
Accepted
C++
0.102
2014-08-30 13:31:48
#include#include #include #include #include #include #include #include #include #include using namespace std; const double eps = 1e-10; struct Point { double x, y; Point(double x = 0, double y = 0) : x(x), y(y) { } bool operator < (const Point& a) const { if(a.x != x) return x < a.x; return y < a.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); } 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 Dist(Point A,Point B){return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (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)); } double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; } double Area2(Point A, Point B, Point C) { return Cross(B-A, C-A); } Vector Rotate(Vector A, double rad) { return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad) + A.y*cos(rad)); } Point GetIntersection(Point P, Vector v, Point Q, Vector w) { Vector u = P-Q; double t = Cross(w, u) / Cross(v, w); return P+v*t; } bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2) { double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1); double c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1); return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0; } double PolygonArea(Point* p, int n) { double area = 0; for(int i = 1; i < n-1; i++) area += Cross(p[i]-p[0], p[i+1]-p[0]); return area; } bool OnSegment(Point p, Point a1, Point a2) { return dcmp(Cross(a1-p, a2-p)) == 0 && dcmp(Dot(a1-p, a2-p)) < 0; } //Square 正方形 //Rectangle 長方形 //Rhombus 菱形 //Parallelogram 平行四邊形 //Trapezium 梯形 //Ordinary Quadrilateral 一般四邊形 Point P[5]; char result[10][30]; void init(){ strcpy(result[1],"Square"); strcpy(result[2],"Rectangle"); strcpy(result[3],"Rhombus"); strcpy(result[4],"Parallelogram"); strcpy(result[5],"Trapezium"); strcpy(result[6],"Ordinary Quadrilateral"); } int Judge(Point a,Point b,Point c,Point d){ Vector v1 = b - a; Vector v2 = c - a; Vector v3 = v1 + v2; if(v3 == (d - a)){ //確定是一個平行四邊形 double L1 = Dist(a,b); double L2 = Dist(a,c); double k = Dot(v1,v2); if(!dcmp(L1 - L2) && !dcmp(k)) return 1; if(!dcmp(k)) return 2; if(!dcmp(L1 - L2)) return 3; else return 4; } else return 0; } int Judge2(Point a,Point b,Point c,Point d){ Vector ab = b - a; Vector bc = c - b; Vector cd = d - c; Vector da = a - d; double ans1 = Cross(ab,cd); double ans2 = Cross(bc,da); if(!dcmp(ans1) || !dcmp(ans2)) return 1; else return 0; } int solve(){ int ans; ans = Judge(P[1],P[2],P[3],P[4]); if(ans) return ans; ans = Judge(P[1],P[3],P[4],P[2]); if(ans) return ans; ans = Judge(P[1],P[2],P[4],P[3]); if(ans) return ans; else{ int ok = 0; ok = Judge2(P[1],P[2],P[3],P[4]); if(ok) return 5; ok = Judge2(P[1],P[3],P[4],P[2]); if(ok) return 5; ok = Judge2(P[1],P[2],P[4],P[3]); if(ok) return 5; } return 6; } int main(){ init(); int T,Case = 1; scanf("%d",&T); while(T--){ for(int i = 1 ; i <= 4 ; i++) scanf("%lf%lf",&P[i].x,&P[i].y); int ans = solve(); printf("Case %d: %s\n",Case ++ ,result[ans]); } return 0; }
