首页 > 代码库 > LightOj1203 - Guarding Bananas(凸包求多边形中的最小角)
LightOj1203 - Guarding Bananas(凸包求多边形中的最小角)
题目链接:http://lightoj.com/volume_showproblem.php?problem=1203
题意:给你一个点集,求凸包中最小的角;模板题,但是刚开始的时候模板带错了,错的我都想吐了;
#include <stdio.h>#include <algorithm>#include <cstring>#include <cmath>using namespace std;#define met(a, b) memset(a, b, sizeof(a))const double eps = 1e-10;const double PI = acos(-1);const int N = 150010;struct point{ double x, y; point(double x=0, double y=0) : x(x), y(y){} friend point operator - (const point& p1, const point& p2) { return point(p1.x-p2.x, p1.y-p2.y); } friend double operator ^ (const point& p1, const point& p2) { return p1.x*p2.y - p1.y*p2.x; }}p[N], res[N];double Dist(point p1, point p2){ double dx = p1.x - p2.x, dy = p1.y - p2.y; return sqrt(dx*dx + dy*dy);}bool cmp1(point p1, point p2){ if(p1.y == p2.y) return p1.x < p2.x; return p1.y < p2.y;}bool cmp2(point p1, point p2)///极角排序;若极角相同,距离近的在前面;{ double k = (p1-p[0])^(p2-p[0]); if( k>eps || (fabs(k)<eps && Dist(p1, p[0]) < Dist(p2, p[0]) )) return 1; return 0;}int Graham(int n){ res[0] = p[0];if(n == 1) return 1; res[1] = p[1];if(n == 2) return 2; int top = 1; for(int i=2; i<n; i++) { while(top && ((res[top]-res[top-1])^(p[i]-res[top-1])) <= 0) top--; res[++top] = p[i]; } return top+1;}int main(){ int n, T, tCase = 1; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i=0; i<n; i++) scanf("%lf %lf", &p[i].x, &p[i].y); sort(p, p+n, cmp1);///p[0]为最下方靠左的点; sort(p+1, p+n, cmp2);///以p[0]为基点,按叉积进行排序; int cnt = Graham(n);///求凸包的顶点个数cnt,保存在res中,下标从0开始; if(cnt < 3) { printf("Case %d: 0\n", tCase++); continue; } double ans = 1000; res[cnt] = res[0], res[cnt+1] = res[1]; for(int i=1; i<=cnt; i++) { double a = Dist(res[i-1], res[i+1]); double b = Dist(res[i-1], res[i]); double c = Dist(res[i], res[i+1]); ans = min(ans, acos((b*b+c*c-a*a)/(2*b*c))); } printf("Case %d: %.6f\n", tCase++, ans*180/PI); } return 0;}
LightOj1203 - Guarding Bananas(凸包求多边形中的最小角)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。