题目描述
农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。
输入输出格式
输入格式：
输入数据的第一行包括一个整数 N。N（0 <= N <= 10,000）表示农夫约翰想要围住的放牧点的数目。接下来 N 行，每行由两个实数组成，Xi 和 Yi,对应平面上的放牧点坐标（-1,000,000 <= Xi,Yi <= 1,000,000）。数字用小数表示。
输出格式：
输出必须包括一个实数，表示必须的围栏的长度。答案保留两位小数。
输入输出样例
输入样例#1：
4 4 8 4 12 5 9.3 7 8
输出样例#1：
12.00
说明
题目翻译来自NOCOW。
USACO Training Section 5.1
解题思路
一道裸的凸包周长。
凸包周长～直径多长～一进考场～全都忘光——
我是从这里学到的姿势，直接上模板吧。
还有，极角排序不能用斜率！要用叉积！
源代码
#include<cmath> #include<cstdio> #include<algorithm> using namespace std; int n; struct node{ double x; double y; double k; bool operator < (const node & a) const{//极角排序 if(fabs(k-a.k)<1e-5) { return (x*x+y*y)<(a.x*a.x+a.y*a.y); } return (k<a.k); } }p[100010]; double X(node a,node b,node c)//叉积 { double x1=b.x-a.x,y1=b.y-a.y; double x2=c.x-a.x,y2=c.y-a.y; return x1*y2-x2*y1; } double len(node a,node b){return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );}//勾股 node s[100010]={0}; int top=0; int main() { scanf("%d",&n); if(n==1||n==0){printf("0");return 0;} for(int i=1;i<=n;i++)//输入 { double x,y; scanf("%lf%lf",&x,&y); p[i]={x,y}; if(p[i].y<p[1].y) swap(p[1],p[i]); else if(fabs(p[i].y-p[1].y)<1e-6&&p[i].x<p[1].x) swap(p[1],p[i]); } if(n==2){printf("%lf",len(p[1],p[2]));return 0;} for(int i=2;i<=n;i++)//挪原点 { p[i].x-=p[1].x; p[i].y-=p[1].y; p[i].k=p[i].y/p[i].x; } p[1]={0.0,0.0}; sort(p+2,p+1+n); s[top++]=p[1]; s[top++]=p[2]; p[++n]=p[1]; for(int i=3;i<=n;i++)//求凸包 { while(top!=0&&X(s[top-2],s[top-1],p[i])<0)top--; s[top++]=p[i]; } double ans=0; //for(int i=1;i<=n;i++) printf("^%lf^%lf^\n",p[i].x,p[i].y); do//求周长 { ans+=len(s[top-1],s[top-2]); top--; }while(top); printf("%.2lf\n",ans); return 0; }
