题目描述

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

输入输出格式

输入格式:

输入数据的第一行包括一个整数 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

题目求的就是凸包的周长,求出凸包以后算一遍就行了。

(下面是我打了一半的二维几何的板子)

/*
这里用来存坑:
1.利用叉积求和三角形面积有关的别忘了除二
2.还差旋转卡壳和半平面交
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<ctime>
#define ll long long
#define maxn 10005
using namespace std;
const double eps=0.000000001;
bool flag=; inline int zt(double x){
if(fabs(x)<=eps) return ;
if(x>) return ;
return -;
} struct node{
double x,y;
//极角
double omega;
//数乘
node operator *(const double& u)const{
return (node){x*u,y*u};
}
//点+向量 or 向量+向量 (点+点没有意义)
node operator +(const node& a)const{
return (node){x+a.x,y+a.y};
}
//点-点得到向量
node operator -(const node& a)const{
return (node){x-a.x,y-a.y};
}
//为了按极角排序
bool operator <(const node& a)const{
return zt(omega-a.omega)==-;
}
}c[maxn],q[maxn],ret[maxn];
//按x第一关键字,y第二关键字升序排序
bool cmp(node x,node y){
if(!zt(x.x-y.x)) return zt(x.y-y.y)<;
else return zt(x.x-y.x)<;
} //判断两个点是否重合
bool eq(node x,node y){
return (!zt(x.x-y.x)&&!zt(x.y-y.y));
} //点积
inline double pointmul(node x,node y){
return x.x*y.x+x.y*y.y;
} //叉积
inline double Xmul(node x,node y){
return x.x*y.y-x.y*y.x;
} //两个向量夹角
inline double getthita(node x,node y){
double now=pointmul(x,y)/pointmul(x,x)/pointmul(y,y);
//acos和asin损失精度比较厉害,所以可以转化成点之后用atan2
return atan2(sqrt(-now*now),now);
} //求一个向量旋转thita角之后得到的向量
inline node rotate(node l,double thita){
double co=cos(thita),si=sin(thita);
return (node){l.x*co-l.y*si,l.x*si+l.y*co};
} //两点间距离
inline double dist(node x,node y){
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
} struct lines{
//点向法表示直线
node base,vec;
}; //两直线交点
inline node pub(lines a,lines b){
return a.base+a.vec*fabs(Xmul(a.base-b.base,b.vec)/Xmul(a.vec,b.vec));
} //求多边形(可以不凸,但是各边不能乱交)
inline double S(node *u,int len){
if(!flag){
//如果不是求出凸包后得到的多边形的话还需要按照极角排序。
//不过如果是求出的凸包之后的多边形极角已经是有序的了。
for(int i=;i<=len;i++) u[i].omega=atan2(u[i].y,u[i].x);
sort(u+,u+len+);
} double an=;
for(int i=;i<=len;i++) an+=Xmul(u[i-],u[i]);
an+=Xmul(u[len],u[]); return an/2.00;
} //把点集u变成一个凸包(而且极角已经有序),并返回凸包上点的个数
inline int get_hill(node *u,int len){
//求凸包的话得按x和y坐标排序
sort(u+,u+len+,cmp);
int tt=,tot=; //下凸包
q[]=u[],q[]=u[],tt=;
for(int i=;i<=len;i++){
while(tt>&&zt(Xmul(q[tt]-q[tt-],u[i]-q[tt]))<) tt--;
q[++tt]=u[i];
}
for(int i=;i<=tt;i++) ret[++tot]=q[i]; //上凸包
q[]=u[],q[]=u[],tt=;
for(int i=;i<=len;i++){
while(tt>&&zt(Xmul(q[tt]-q[tt-],u[i]-q[tt]))>) tt--;
q[++tt]=u[i];
}
for(int i=tt;i;i--) if(!eq(q[i],ret[tot])&&!eq(q[i],ret[])) ret[++tot]=q[i]; for(int i=;i<=tot;i++) u[i]=ret[i];
flag=;
return tot;
} int n;
double B; inline void solve(int problem_id){
if(problem_id==){
scanf("%d%lf",&n,&B);
for(int i=;i<=n;i++) scanf("%lf%lf",&c[i].x,&c[i].y);
printf("%.4lf\n",B*S(c,n));
} if(problem_id==){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%lf%lf",&c[i].x,&c[i].y);
n=get_hill(c,n); double ans=;
for(int i=;i<=n;i++) ans+=dist(c[i],c[i-]);
ans+=dist(c[],c[n]); printf("%.2lf\n",ans);
}
} int main(){
srand(time());
solve(rand()%+);
return ;
}

最新文章

  1. css/js(工作中遇到的问题)-4
  2. 学习SAP HANA SQL
  3. 笔记--mysql rpm 安装
  4. IOS开发——使用数据库
  5. redis’五种格式的存储与展示
  6. 在Myeclipse中配置Maven
  7. iOS开发小技巧--高斯模糊框架的应用
  8. 实例介绍Cocos2d-x开关菜单
  9. 九度OJ 1349 数字在排序数组中出现的次数 -- 二分查找
  10. NuGet学习笔记(1)——初识NuGet及快速安装使用(转)
  11. swipejs
  12. [原创]linux简单之美(一)
  13. STL: generate ,geterate_n
  14. ajax无法跳转页面的问题,
  15. GetLastError() 返回值含义
  16. windowSoftInputMode键盘把输入框挡住了
  17. Segments POJ 3304 直线与线段是否相交
  18. 低版本IE内核浏览器兼容placeholder属性解决办法
  19. 启动eclipse时候提示错误Error:Could not create the Java Virtual Machine. Error:A Fatal exception has occurred,Program will exit.
  20. web服务器案例

热门文章

  1. 【BZOJ4325】NOIP2015 斗地主 搜索+贪心
  2. linux 条件判断式
  3. 洛谷P1339 热浪
  4. POJ2912:Rochambeau(带权并查集)
  5. MongoDB加索引
  6. 浅析 nth-child(n) 和 nth-of-type(n)
  7. javascript学习3
  8. shell脚本复制文件夹内容到另外的文件夹,如果存在则自动备份
  9. [Leetcode Week6]Best Time to Buy and Sell Stock
  10. pinctrl框架