1 //找到一个点，看是否右侧有点，有则从新找点，如果该点右侧没有点，则是凸包上的一点，每次都找到最右边的一条边 2  3 #include<stdio.h> 4 #include<algorithm> 5 #include<string.h> 6 #include<math.h> 7 using namespace std; 8 int n,sta; 9 struct dian10 {11     double x;12     double y;13 } p[1001];14 int cmp(dian a,dian b)15 {16     if(a.y==b.y)17         return a.x<b.x;18     return a.y<b.y;19 }20 double diss(int i,int j)21 {22     return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));23 }24 int find(int ce)25 {26     for(int i=0; i<n; i++)27     {28         if (ce==sta||i==ce)29             continue;30         if ((p[i].x-p[sta].x)*(p[ce].y-p[sta].y)-(p[i].y-p[sta].y)*(p[ce].x-p[sta].x)>0)31             return 2;32     }33     if (ce==0)34         return 0;35     return 1;36 37 }38 int main()39 {40     double l;41     while(scanf("%d%lf",&n,&l)!=EOF)42     {43         int i,j,vis[1001];44         double sum=0;45         sta=0;46         memset(vis,0,sizeof(vis));47         for(i=0; i<n; i++)48             scanf("%lf%lf",&p[i].x,&p[i].y);49         sort(p,p+n,cmp);50         while(1)51         {52             for(i=0; i<n; i++)53             {54                 if (vis[i]||sta==i)55                     continue;56                 int flag=find(i);57                 if (flag==2)58                     continue;59                 if (!flag)60                 {61                     sum+=diss(i,sta);62                     sum+=3.14159*2*l;63                     int sum1=sum;64                     if(sum-0.5>=sum1)65                         printf("%d\n",sum1+1);66                     else67                         printf("%d\n",sum1);68                     return 0;69                 }70                 sum+=diss(i,sta);71                 sta=i;72                 vis[i]=1;73             }74         }75     }76     return 0;77 }

  1 //通过建立临时凸包，判别队列前两个点和此时点是否符合要求，如果符合进队列，不符合top-1改点出队列，然后再比较队列前两个点和此时点是否符合要求，如果符合进队列....  2   3 #include <algorithm>  4 #include <iostream>  5 #include <sstream>  6 #include <cstdlib>  7 #include <cstring>  8 #include <cstdio>  9 #include <string> 10 #include <bitset> 11 #include <vector> 12 #include <queue> 13 #include <stack> 14 #include <cmath> 15 #include <list> 16 //#include <map> 17 #include <set> 18 using namespace std; 19 /***************************************/ 20 #define ll long long 21 #define int64 __int64 22 #define PI 3.1415927 23 /***************************************/ 24 const int INF = 0x7f7f7f7f; 25 const double eps = 1e-8; 26 const double PIE=acos(-1.0); 27 const int d1x[]= {0,-1,0,1}; 28 const int d1y[]= {-1,0,1,0}; 29 const int d2x[]= {0,-1,0,1}; 30 const int d2y[]= {1,0,-1,0}; 31 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 32 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 34 /***************************************/ 35 void openfile() 36 { 37     freopen("data.in","rb",stdin); 38     freopen("data.out","wb",stdout); 39 } 40 priority_queue<int> qi1; 41 priority_queue<int, vector<int>, greater<int> >qi2; 42 /**********************华丽丽的分割线,以上为模板部分*****************/ 43  44 struct node 45 { 46     double x,y; 47     double angle; 48 }p[1005]; 49 int cmp1(node a1,node a2) 50 { 51     if (a1.y==a2.y) 52         return a1.x<a2.x; 53     return a1.y<a2.y; 54 } 55 int cmp2(node a1,node a2) 56 { 57     if (a1.angle==a2.angle) 58         return a1.x<a2.x; 59     return a1.angle<a2.angle; 60 } 61 int EPS(double f) 62 { 63     if (fabs(f)<eps) 64         return 0; 65     return f>0?1:-1; 66 } 67 double getangle(node a1,node a2) 68 { 69     return atan2(a2.y-a1.y,a2.x-a1.x); 70 } 71 double cha(node b1,node a1) 72 { 73     return a1.x*b1.y-a1.y*b1.x; 74 } 75 double dis(node a,node b) 76 { 77     return sqrt((b.y-a.y)*(b.y-a.y)+(b.x-a.x)*(b.x-a.x)); 78 } 79 int n; 80 double r; 81 int judge(node a,node b,node c) 82 { 83     int m=(a.x-b.x)*(c.y-b.y); 84     int m1=(a.y-b.y)*(c.x-b.x); 85     m=m-m1; 86     if (m>0) 87         return 1; 88     return 0; 89 } 90 int main() 91 { 92  93     while(scanf("%d%lf",&n,&r)!=EOF) 94     { 95         int i,j; 96         for(i=0;i<n;i++) 97             scanf("%lf%lf",&p[i].x,&p[i].y); 98         sort(p,p+n,cmp1); 99         for(i=0;i<n;i++)100             p[i].angle=getangle(p[0],p[i]);101         sort(p,p+n,cmp2);102         node que[1001];103         que[0]=p[0];104         que[1]=p[1];105         que[2]=p[2];106         int top=2;107         for(i=3;i<n;i++)108         {109             while(top>=1&&judge(que[top-1],que[top],p[i]))110             {111                 top--;112             }113             que[++top]=p[i];114         }115         double sum=0;116         for(i=0;i<top;i++)117            sum+=dis(que[i],que[i+1]);118         sum+=dis(que[top],que[0]);119         sum+=2*PI*r;120         printf("%.0lf\n",sum);121     }122     return 0;123 }