HDU 1392 Surround the Trees 构造凸包
又是一道模板题
#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <queue>#include <cmath>#include <algorithm>using namespace std;struct P{ int x,y; double angle;} p[50010];bool cmp(P p1,P p2){ if(p1.angle > p2.angle) return true; if(p1.angle == p2.angle && p1.y < p2.y) return true; if(p1.angle == p2.angle && p1.y == p2.y && p1.x < p2.x) return true; return false;}double calangle(P p,P t){ return ((t.x-p.x)*(t.x-p.x) + 1 - (t.x-p.x-1)*(t.x-p.x-1))/(2*sqrt((t.x-p.x)*(t.x-p.x) + (t.y-p.y)*(t.y-p.y)));}P sp[50010];bool judgesite(P p1,P p2, P p){ P l1,l2; l1.x = p2.x - p1.x; l1.y = p2.y - p1.y; l2.x = p.x - p1.x; l2.y = p.y - p1.y; return (l1.x*l2.y - l1.y*l2.x) > 0 ? true : false ;}double callen(P p1,P p2){ return sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) );}int main(){ int n,i; int top; double MinLen; while(scanf("%d",&n) && n) { top = 0; for(i = 1; i <= n; ++i) { scanf("%d %d",&p[i].x,&p[i].y); } P temp; for(temp = p[1],i = 2; i <= n; ++i) { if(temp.y > p[i].y) { temp = p[i]; } else if(temp.y == p[i].y && temp.x > p[i].x) { temp = p[i]; } } for(i = 1; i <= n; ++i) { if(temp.x != p[i].x || temp.y != p[i].y) { p[i].angle = calangle(temp,p[i]); } else p[i].angle = -2; } sort(p+1,p+n+1,cmp); sp[top++] = p[n]; sp[top++] = p[1]; for(i = 2; i <= n;) { if(judgesite(sp[top-2],sp[top-1],p[i])) { sp[top++] = p[i]; ++i; } else top--; } top--;//最后一个点重复了 MinLen = callen(sp[top-1],sp[0]); for(i = 1; i < top; ++i) { MinLen += callen(sp[i-1],sp[i]); } printf("%.2lf\n",MinLen); } return 0;}