1.poj1113 Wall

题目：

题意：用一条线把若干个点包起来，并且线距离任何一个点的距离都不小于r。求这条线的最小距离是多少？

分析：这道题的答案是凸包周长加上一个圆周长，即包围凸包的一个圆角多边形，但是没弄明白那些圆角加起来为什么恰好是一个圆。每个圆角是以凸包对应的顶点为圆心，给定的L为半径，与相邻两条边的切点之间的一段圆弧。每个圆弧的两条半径夹角与对应的凸包的内角互补。假设凸包有n条边，则所有圆弧角之和为180°*n-180°*（n-2）=360°。故，围墙周长为=n条平行于凸包的线段+n条圆弧的长度=凸包周长+围墙离城堡距离L为半径的圆周长。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 const int maxn=1010;  7 const double eps=1e-8;  8 const double pi=acos(-1.0);  9 inline double sqr(double x){
    return x*x;} 10 int sgn(double x){ 11     if (fabs(x)
          
           0; 69         } 70     }; 71     //极角排序  先找到左下角的点  72     //重载好point的'<'  73     void norm(){ 74         point mi=p[0]; 75         for (int i=1;i
           
            1 && sgn((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2]))<=0) top--; 94 convex.p[top++]=p[i]; 95 } 96 if (convex.n==2 && (convex.p[0]==convex.p[1])) convex.n--; 97 } 98 }; 99 polygon C;100 int main(){101 int n,L; cin >> n >> L;102 double x,y;103 for (int i=0;i
            
             > x >> y;105 C.add(point(x,y));106 }107 polygon ans;108 C.Graham(ans);109 ans.getline();110 double res=0;111 for (int i=0;i
            
           
          
         
        
       
      

（为了套板子，写的很繁琐）

2.poj2007 Scrambled Polygon

题目：

题意：求一个凸多边形的凸包。要求起始点为输入的第一个点。

分析：rt。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const double eps=1e-8; 7 const int maxn=55; 8 inline double sqr(int x){
    return x*x*1.0;} 9 int sgn(double x){10     if (fabs(x)
          
           0;55         }56     };57     //极角排序  先找到左下角的点 58     //重载好point的'<' 59     void norm(){60         point mi=p[0];61         for (int i=1;i
           
            1 && sgn(((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2]))*1.0)<=0) top--;80 convex.p[top++]=p[i];81 }82 if (convex.n==2 && (convex.p[0]==convex.p[1])) convex.n--;83 } 84 };85 polygon C;86 int main(){87 int x,y; point p;88 C.n=0; 89 cin >> x >> y; p=point(x,y); C.add(p);90 while (cin >> x >> y) C.add(point(x,y));91 polygon ans;92 C.Graham(ans); int k;93 for (int i=0;i
           
          
         
        
       
      

3.poj1228

　　题目：

题意：输入一个凸包上的点（没有凸包内部的点，要么是凸包顶点，要么是凸包边上的点），判断这个凸包是否稳定。所谓稳定就是判断能不能在原有凸包上加点。

分析：问凸包是否稳定。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const double eps=1e-8; 7 const int maxn=1010; 8 int sgn(double x){ 9     if (fabs(x)
          
           1 && ((pp[m-1]-pp[m-2])^(p[i]-pp[m-2]))<0) m--;30         pp[m++]=p[i];31     } 32     int k=m;33     for (int i=n-2;i>=0;i--){34         while (m>k && ((pp[m-1]-pp[m-2])^(p[i]-pp[m-2]))<0) m--;35         pp[m++]=p[i];36     }37     return m-1;38 }39 bool check(point p[],int n){40     for (int i=1;i
           
            > t;48 while (t--){49 cin >> n;50 for (int i=0;i
            
             > p[i].x >> p[i].y;51 if (n<6){cout << "NO\n";continue;}52 int cnt=convexhull(p,n,pp);53 if (check(pp,cnt)) cout << "YES\n"; else cout << "NO\n";54 }55 return 0;56 }
            
           
          
         
        
       
      

 

4

5.poj3348 Cows

题目：

题意：给出一些点圈出一个最大面积每50平方养一头牛问最多能养多少牛。

分析：凸包+多边形面积。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 const int maxn=10005;  7 inline int sqr(int x){
    return x*x;}  8 struct point{  9     int x,y; 10     point(){} 11     point(int _x,int _y):x(_x),y(_y){} 12     //判断两点相同  13     bool operator ==(const point &b) const{   14         return x-b.x==0 && y-b.y==0; 15     } 16     //  17     point operator -(const point &b) const{ 18         return point(x-b.x,y-b.y); 19     }  20     //叉积  21     int operator ^(const point &b) const{ 22         return x*b.y-y*b.x;  23     } 24     //点积 25     int operator *(const point &b) const{ 26         return x*b.x+y*b.y; 27     }  28     //重载小于号   （求最左下角的点 29     bool operator <(const point &b)const{ 30         return x-b.x==0?y-b.y<0:x
          
           0; 55         } 56     }; 57     //极角排序  先找到左下角的点  58     //重载好point的'<'  59     void norm(){ 60         point mi=p[0]; 61         for (int i=1;i
           
            1 && ((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2]))<=0) top--; 80 convex.p[top++]=p[i]; 81 } 82 if (convex.n==2 && (convex.p[0]==convex.p[1])) convex.n--; 83 } 84 int getarea(){ 85 int sum=0; 86 for (int i=0;i
            
             > n; C.n=0; 93 for (int i=0;i
             
              > x >> y; 95 C.add(point(x,y)); 96 } 97 polygon ans; C.Graham(ans); 98 cout << ans.getarea()/50 << endl; 99 return 0;100 }
             
            
           
          
         
        
       
      

 6.poj1259/hdoj6219

题意：给出n个点，求出最大面积的凸包且凸包内不包含原点集中的点。

分析：rt。求最大面积空凸包。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const double eps=1e-8; 7 const int maxn=1005;  8 inline double sqr(double x){
    return x*x;} 9 int sgn(double x){10     if (fabs(x)
          
           =0 && ((p[i]-o)^(p[j]-o))==0) j--;47         bool flag=(j==i-1);48         while (j>=0){49             int k=j-1;50             while (k>=0 && ((p[i]-p[k])^(p[j]-p[k]))>0) k--;51             double area=fabs((p[i]-o)^(p[j]-o))/2.0;52             if (k>=0) area+=dp[j][k];53             if (flag) dp[i][j]=area;54             ans=max(ans,area);55             j=k;56         }57         if (flag){58             for (int j=1;j
           
            0;69 return dist(a,tmp)
            
             tmp.y || p[j].y==tmp.y && p[j].x>tmp.x) pp[cnt++]=p[j];78 }79 sort(pp,pp+cnt,cmp_angle); //根据极角排序80 ans=max(ans,empty_convex(pp,cnt,tmp)); 81 }82 return ans;83 }84 int main(){85 int t,n; cin >> t;86 while (t--){87 cin >> n;88 for (int i=0;i
             
              > p[i].x >> p[i].y;89 double ans=largest_empty_convex(p,n);90 printf("%.1f\n",ans);91 }92 return 0;93 }