国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > UVA 11800 - Determine the Shape(计算几何)

UVA 11800 - Determine the Shape(计算几何)

来源:程序员人生   发布时间:2015-04-09 08:38:31 阅读次数:3662次

题意:给定4个点,判断形状

思路:先求个凸包,就可以把4个点排序,然后就是利用几何去判断,利用点积判垂直,利用叉积判平行

还有这题有个坑啊,明明说好是没有点共线的,实际上是有的,所以求凸包如果不是4个点,直接输出不规则4边形便可

代码:

#include <cstdio> #include <cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int MAXN = 4; struct Point { int x, y; Point() {} Point(double x, double y) { this->x = x; this->y = y; } void read() { scanf("%d%d", &x, &y); } } list[MAXN], p[MAXN]; typedef Point Vector; Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); } Vector operator - (Vector A, Vector 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 Dot(Vector A, Vector B) {return A.x * B.x + A.y * B.y;} //点积 int Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;} //叉积 int stack[MAXN], top; int xmult(Point p0, Point p1, Point p2) { return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x); } double dist(Point p1,Point p2) { return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y)); } int dist2(Point p1, Point p2) { return (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y); } //极角排序函数 , 角度相同则距离小的在前面 bool cmp(Point p1,Point p2) { int tmp= xmult(list[0], p1, p2); if(tmp > 0) return true; else if(tmp == 0 && dist(list[0], p1) < dist(list[0], p2)) return true; else return false; } bool LineParallel(Vector v, Vector w) { return Cross(v, w) == 0; } bool LineVertical(Vector v, Vector w) { return Dot(v, w) == 0; } //输入并把最左下方的点放在list[0]并且进行极角排序 void init(int n) { int i, k; Point p0; scanf("%d%d", &list[0].x, &list[0].y); p0.x = list[0].x; p0.y = list[0].y; k = 0; for(i = 1; i < n; i++) { scanf("%d%d", &list[i].x, &list[i].y); if((p0.y > list[i].y) || ((p0.y == list[i].y) && (p0.x > list[i].x))) { p0.x = list[i].x; p0.y = list[i].y; k = i; } } list[k] = list[0]; list[0] = p0; sort(list + 1, list + n, cmp); } void graham(int n) { int i; if(n == 1) {top = 0; stack[0] = 0;} if(n == 2) { top = 1; stack[0] = 0; stack[1] = 1; } if(n > 2) { for(i = 0; i <= 1; i++) stack[i] = i; top = 1; for(i = 2; i < n; i++) { while(top > 0 && xmult(list[stack[top - 1]], list[stack[top]], list[i]) <= 0) top--; top++; stack[top]=i; } } for (int i = 0; i <= top; i++) p[i] = list[stack[i]]; } int t; void solve() { if (LineParallel(p[1] - p[0], p[2] - p[3]) && LineParallel(p[2] - p[1], p[3] - p[0])) { if (LineVertical(p[1] - p[0], p[2] - p[1]) && LineVertical(p[2] - p[1], p[3] - p[2]) && LineVertical(p[0] - p[3], p[3] - p[2])) { if (dist2(p[1], p[0]) == dist2(p[2], p[1])) printf("Square "); else printf("Rectangle "); } else { if (dist2(p[1], p[0]) == dist2(p[2], p[1])) printf("Rhombus "); else printf("Parallelogram "); } } else if (LineParallel(p[1] - p[0], p[2] - p[3]) || LineParallel(p[2] - p[1], p[3] - p[0])) printf("Trapezium "); else printf("Ordinary Quadrilateral "); } int main() { int cas = 0; scanf("%d", &t); while (t--) { init(4); graham(4); printf("Case %d: ", ++cas); if (top < 3) { printf("Ordinary Quadrilateral "); continue; } for (int i = 0; i < 4; i++) p[i] = list[stack[i]]; solve(); } return 0; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生