www.cnblogs.com/shaokele/

---

luoguP2742 二维凸包 / 圈奶牛Fencing the Cows

　　Time Limit: 1 Sec

　　Memory Limit: 128 MB

Description

　　农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。

　

Input

　　输入数据的第一行包括一个整数 N。N（0 <= N <= 10,000）表示农夫约翰想要围住的放牧点的数目。接下来 N 行，每行由两个实数组成，Xi 和 Yi,对应平面上的放牧点坐标（-1,000,000 <= Xi,Yi <= 1,000,000）。数字用小数表示。

　　

Output

　　输出必须包括一个实数，表示必须的围栏的长度。答案保留两位小数。

　　

Sample Input

　　4

　　4 8

　　4 12

　　5 9.3

　　7 8

　

Sample Output

　　12.00

　　

题目地址：　　

题目大意： 题目已经很简洁了>_<

题解：

　　裸的凸包

　　我用 graham 做

　　graham 是什么请自行百度

　　大致就是找图中最左下角的点

　　把其他点按与他连线边的斜率排序

　　用一个栈来维护，先加入三个点

　　如果新加进的点使得栈顶的点变凹了

　　把栈顶的点弹出

　　弹完点之后把这个点加进来

　　最后再把起点加进去

　　把整个图连起来

---

AC代码

#include 
    
      #include 
     
      #include 
      
       using namespace std;const int N=10005;int n;double ans;struct data{    double x,y;}p[N],f[N];double dis(data a,data b){    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}double mul(data a,data b,data p){    return (a.x-p.x)*(b.y-p.y)-(b.x-p.x)*(a.y-p.y);       // (a.x-p.x)/(a.y-p.y)>(b.x-p.x)/(b.y-p.y) 叉积}inline bool cmp(data a,data b){    if(mul(a,b,p[1])==0)return dis(a,p[1])
       
        0;}void graham(){    int k=1;    for(int i=2;i<=n;i++)        if(p[i].y
        
         
          =1 && mul(p[i],f[top],f[top-1])>=0) top--; f[++top]=p[i]; } f[++top]=p[1]; for(int i=1;i