luoguP2742二维凸包/圈奶牛FencingtheCows

www.cnblogs.com/shaokele/

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

　　Time Limit: 1 Sec
　　Memory Limit: 128 MB

Description

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

Input

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

Output

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

Sample Input

　　4
　　4 8
　　4 12
　　5 9.3
　　7 8
　

Sample Output

　　12.00
　　

题目地址&＃xff1a;　　luoguP2742 二维凸包 / 圈奶牛Fencing the Cows

题目大意&＃xff1a; 题目已经很简洁了>_<

题解&＃xff1a;

　　裸的凸包
　　我用 graham 做
　　graham 是什么请自行百度
　　大致就是找图中最左下角的点
　　把其他点按与他连线边的斜率排序
　　用一个栈来维护&＃xff0c;先加入三个点
　　如果新加进的点使得栈顶的点变凹了
　　把栈顶的点弹出
　　弹完点之后把这个点加进来
　　最后再把起点加进去
　　把整个图连起来

AC代码

#include
#include
#include
using namespace std;
const int N&＃61;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)&＃43;(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])&＃61;&＃61;0)return dis(a,p[1])0;
}
void graham(){int k&＃61;1;for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;)if(p[i].y&＃61;1 && mul(p[i],f[top],f[top-1])>&＃61;0)top--;f[&＃43;&＃43;top]&＃61;p[i];}f[&＃43;&＃43;top]&＃61;p[1];for(int i&＃61;1;i}
int main(){scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%lf%lf",&p[i].x,&p[i].y);graham();printf("%.2lf\n",ans);return 0;
}