首页 > 代码库 > [HDU1392]Surround the Trees
[HDU1392]Surround the Trees
思路：
凸包模板题。
注意n=1和n=2的情况。
当n=1时，不需要绳子。
当n=2时，绳子长度为两棵树之间距离。
当n≥e时，Graham求凸包即可。最后将凸包上的所有相邻点距离求和。
1 #include<cmath> 2 #include<cstdio> 3 #include<cctype> 4 #include<algorithm> 5 inline int getint() { 6 char ch; 7 while(!isdigit(ch=getchar())); 8 int x=ch^‘0‘; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^‘0‘);10 return x;11 }12 struct Point {13 int x,y;14 Point operator - (const Point &x) const {15 return (Point){this->x-x.x,this->y-x.y};16 }17 int operator * (const Point &x) const {18 return this->x*x.y-x.x*this->y;19 }20 };21 int dist2(const Point x,const Point y) {22 return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);23 }24 double dist(const Point x,const Point y) {25 return sqrt(dist2(x,y));26 }27 const int N=101;28 Point p[N];29 bool operator < (const Point &p1,const Point &p2) {30 int s=(p1-p[0])*(p2-p[0]);31 return s<0||(!s&&(dist2(p1,p[0]))>=dist2(p2,p[0]));32 }33 bool judgeOnLeft(int p0,int p1,int p2) {34 double s=(p[p1]-p[p0])*(p[p2]-p[p0]);35 return s<0||(!s&&(dist2(p[p1],p[p0]))>=dist2(p[p2],p[p0]));36 }37 inline void swap(Point &a,Point &b) {38 Point t;39 t=a;40 a=b;41 b=t;42 }43 int main() {44 int n;45 while(n=getint()) {46 if(n==1) {47 puts("0.00");48 continue;49 }50 if(n==2) {51 Point a,b;52 a.x=getint(),a.y=getint();53 b.x=getint(),b.y=getint();54 printf("%.2f\n",dist(a,b));55 continue;56 }57 int k=0;58 for(int i=0;i<n;i++) {59 p[i].x=getint(),p[i].y=getint();60 if((p[i].x<p[k].x)||((p[i].x==p[k].x)&&(p[i].y<p[k].y))) k=i;61 }62 swap(p[0],p[k]);63 std::sort(&p[1],&p[n]);64 p[n]=p[0];65 int s[N],top=1;66 s[0]=0;67 s[1]=1;68 for(int i=2;i<=n;i++) {69 while(top&&judgeOnLeft(s[top-1],i,s[top])) top--;70 s[++top]=i;71 }72 s[top]=s[0];73 double ans=0;74 for(int i=1;i<=top;i++) {75 ans+=dist(p[s[i]],p[s[i-1]]);76 }77 printf("%.2f\n",ans);78 }79 return 0;80 }
[HDU1392]Surround the Trees
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。