HDU1392SurroundtheTrees（计算几何--凸包）
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1392
题意：计算凸包并求周长
题解;见代码
#include <iostream>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
const ll inf=6666666;
struct NODE{
int x,y;
};
NODE tr[105],l[105];
int t,top;
bool cmp(NODE a,NODE b)
{
double A=atan2(a.y-tr[1].y,a.x-tr[1].x);
double B=atan2(b.y-tr[1].y,b.x-tr[1].x);
if(A!=B) return A<B;
else return a.x<b.x;
}
int Cross(NODE a,NODE b,NODE c)
{
return (a.x-b.x)*(b.y-c.y)-(a.y-b.y)*(b.x-c.x);
}
void Get()
{
int k;
tr[0]=NODE{inf,inf};
for(int i=1;i<=t;i++)
if(tr[0].y>tr[i].y||(tr[0].y==tr[i].y&&tr[0].x>tr[i].x))
{
tr[0]=tr[i];
k=i;
}
swap(tr[k],tr[1]);
sort(tr+2,tr+t+1,cmp);
l[0]=tr[1]; l[1]=tr[2]; top=1;
for(int i=3;i<=t;)
{
if(top&&(Cross(l[top-1],tr[i],l[top])>=0)) top--;
else l[++top]=tr[i++];
}
}
inline double cal(NODE f,NODE g)
{
return sqrt(1ll*(f.x-g.x)*(f.x-g.x)+1ll*(f.y-g.y)*(f.y-g.y));
}
inline void Getans()
{
double ans=0;
if(top==0)
ans=0;
else if(top==1)
ans+=cal(l[0],l[1]);
else {
l[++top]=l[0];
for(int i=0;i<top;i++)
{
ans+=cal(l[i],l[i+1]);
}
}
printf("%.2lf
",ans);
}
int main()
{
while(scanf("%d",&t)&&t)
{
for(int i=1;i<=t;i++)
{
scanf("%d %d",&tr[i].x,&tr[i].y);
}
Get();
Getans();
}
return 0;
}
优质内容筛选与推荐>>1、Android实现选择题答题（包括单选、多选和答题卡）
2、JSP编译原理图解
3、[Hive_add_5] Hive 的 join 操作
4、Git基础
5、RestFramework之视图组件