题目:Hdu1392 Surround the Trees
http://acm.hdu.edu.cn/showproblem.php?pid=1392
image.png
image.png
简易描述：在坐标上求能将所有点都包上的点集，并计算他们的长度
算法步骤：
算法参考：http://www.pianshen.com/article/763090525/
original[102]指原始输入的数据的数组。
Convex [102]在凸包上的点的数组。
1、首先判断如果original中元素个数，如果是1,2单独处理，否则进入2。
2、选出最左下角的元素，将original数组按y坐标排序，得到Convex[0]=original[0]。
3、将original[]剩下的n-1个元素按极角进行排序（相对于Convex[0]的arctan值）。
4、Convex[]中初始时有两个元素，Convex[0]和Convex[1]（最小的极角那个点一定在凸包上）。
5、写一个while，终止条件为扫描original到最后一个点。具体while操作见6。
6、取Convex[]最后两个元素，与当前original[i]进行叉积判断，如果三点是逆时针方向则original[i]加入到Convex[]。
否则将Convex[]最后一个元素删掉（因为不满足），将original[i]加入到Convex[]。注意此处需要回溯，判断删掉后当前的三个元素是否符合。
7、最后Convex[]为凸包上的点集。计算一下点点距，相加即可。
#include<bits/stdc++.h>
#define datatype point
#define INF 1e-16
using namespace std;
struct point
{
int x;
int y;
};
datatype original[102];
datatype Convex [102];
double distance1(datatype a,datatype b)
{
double result=sqrt((b.x-a.x)*(b.x-a.x)*1.0+(b.y-a.y)*(b.y-a.y)*1.0);
return result;
}
bool cmp1(point a,point b)
{
if(a.y==b.y)
return a.x<b.x;//升序
else
return a.y<b.y;
}
bool cmp2(point a,point b)//极角排序
{
int xx=Convex[0].x;
int yy=Convex[0].y;
//double m1=atan2(a.y-yy,a.x-xx);
//double m2=atan2(b.y-yy,b.x-xx);
//if(m1!=m2)
if(fabs(atan2(a.y-yy,a.x-xx)-atan2(b.y-yy,b.x-xx))>INF)
return (atan2(a.y-yy,a.x-xx))<(atan2(b.y-yy,b.x-xx));
return a.x<b.x;
}
double cww(datatype a,datatype b,datatype c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
int main()
{
int n;
while(cin>>n&&n)
{
cout<<fixed;
for(int i=0;i<n;i++)
{
cin>>original[i].x>>original[i].y;
}
if(n==1)
{
double re=0;
cout<<setprecision(2)<<re<<endl;
}
else if(n==2)
{
double re=distance1(original[0],original[1]);
cout<<setprecision(2)<<re<<endl;
}
else
{
//对坐标排序，选出最小坐标
sort(original,original+n,cmp1);
Convex[0]=original[0];
//对n-1个元素进行极角排序
sort(original+1,original+n,cmp2);
Convex[1]=original[1];
int index=2;//循环变量，到original就停
int sum=1;//凸包中的元素个数
while(index<n)
{
while(cww(Convex[sum-1],Convex[sum],original[index])<=0)
sum--;
Convex[++sum]=original[index++];
}
double result=0;
for(int j=1;j<=sum;j++)
{
result+=distance1(Convex[j-1],Convex[j]);
}
result+=distance1(Convex[sum],Convex[0]);
cout<<setprecision(2)<<result<<endl;
}
}
return 0;
}
}
输入：
9
12 7
24 9
30 5
41 9
80 7
50 87
22 9
45 1
50 7
0
运行结果
image.png
此程序在写cmp2时涉及到浮点数的比较，最初没注意，排序一直有问题，浮点数的比较一定不要用a==b!!!具体原因阐述在：https://www.jianshu.com/p/33e899b266f9
