首页 > 代码库 > 洛谷 P2742 [USACO5.1]圈奶牛Fencing the Cows
洛谷 P2742 [USACO5.1]圈奶牛Fencing the Cows
题目描述
农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。
输入输出格式
输入格式：
输入数据的第一行包括一个整数 N。N（0 <= N <= 10,000）表示农夫约翰想要围住的放牧点的数目。接下来 N 行，每行由两个实数组成，Xi 和 Yi,对应平面上的放牧点坐标（-1,000,000 <= Xi,Yi <= 1,000,000）。数字用小数表示。
输出格式：
输出必须包括一个实数，表示必须的围栏的长度。答案保留两位小数。
输入输出样例
输入样例#1：
44 84 125 9.37 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;}
洛谷 P2742 [USACO5.1]圈奶牛Fencing the Cows
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。