题目描述
There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him?
The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line.
输入说明
The input contains one or more data sets. At first line of each input data set is number of trees in this data set, it is followed by series of coordinates of the trees. Each coordinate is a positive integer pair, and each integer is less than 32767. Each pair is separated by blank.
Zero at line for number of trees terminates the input for your program.
输出说明
The minimal length of the rope. The precision should be 10^-2.
输入样例
9
12 7
24 9
30 5
41 9
80 7
50 87
22 9
45 1
50 7
0
输出样例
243.06
分析
本题给了我们n个点,要求我们将这些点全部圈起来,然后求最后的最小周长。
由此想到凸包。
在二维欧几里得空间中,凸包可想象为一条刚好包著所有点的橡皮圈。
求解凸包需要用到Graham扫描法O(n㏒n)
Graham算法步骤:
- 取当前的所有点集中最下面的点P0,如果有和P0点在同一y轴方向上的,则选取这些点中最左边的点作为坐标原点。(x最小)
-
从P0点开始按逆时针方向逐个找凸包上的点,实际上就是进行极角排序,然后对其查询使用。
-
创建一个栈p,把前两个点加入到栈中,如果栈元素大于等于2并且栈顶的点和当前点,栈顶下方的点的叉积<=0,则让栈顶的点出栈。重复上述步骤直到第n个点。
-
计算凸包上每两点之间的距离
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
int n,tt;
struct node{
double x,y;
bool operator<(const node &p) const{
if(y==p.y) return x<p.x;
return y<p.y;
}
}point[N],p0;
int p[N];
double ans;
double cross(node p,node a,node b) //求叉积
{
return ((a.x-p.x)*(b.y-p.y)-(b.x-p.x)*(a.y-p.y));
}
double dis(node a,node b) //求a,b两点间的距离
{
return sqrt((a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
}
bool cmp(node a,node b) //根据叉乘计算幅角θ,按从小到大顺序排序
{
auto t=cross(p0,a,b);
if(t>0) return 1;
if(t==0 && (dis(p0,a)-dis(p0,b))<=0) return 1;
return 0;
}
void graham(int n) //graham算法,处理n个点,找到凸包上的点
{
tt=2;
p[1]=1;
p[2]=2;
for(int i=3;i<=n;i++)
{
while(tt>=2 && cross(point[p[tt-1]],point[p[tt]],point[i])<=0) tt--; //如果当前叉积<=0,说明存在凹包,需要出栈,直到叉积>0为止
p[++tt]=i; //当前点加入栈
}
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>n)
{
if(n==0) break;
memset(point,0,sizeof point); //清空点数组
for(int i=1;i<=n;i++) cin>>point[i].x>>point[i].y;
if(n==1){
printf("0.00\n"); //只有一个点,直接输出0
continue;
}
if(n==2){
printf("%.2lf\n",dis(point[1],point[2])); //两个点,输出两点之间的距离
continue;
}
sort(point+1,point+1+n); //选出起始点p
p0=point[1];
sort(point+2,point+1+n,cmp); //对第一个点后的所有点进行排序
graham(n);
ans=0;
for(int i=2;i<=tt;i++)
{
ans+=dis(point[p[i]],point[p[i-1]]); //加上凸包上每个点的距离
}
ans+=dis(point[p[1]],point[p[tt]]); //加上第一个点和凸包最后一个点的距离
printf("%.2lf\n",ans);
}
return 0;
}