hdu 1392 Surround the Trees

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1392

题意:给出一些点的坐标,求最小的凸多边形把所有点包围时此多边形的周长。

解法:凸包ConvexHull 模板题

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define inf 0x7fffffff
#define PI 3.141592654
#define exp 1e-10
using namespace std;
struct Point
{
double x,y;
Point (double x=,double y=):x(x),y(y){}
friend bool operator < (Point A,Point B)
{
if (A.x != B.x) return A.x < B.x;
return A.y<B.y;
}
}an[];
typedef Point Vector;
Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x , A.y+B.y); }
Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x , A.y-B.y); } int dcmp(double x)
{
if (fabs(x)<exp) return ;
else return x< ? - : ;
}
double cross(Vector A,Vector B)
{
return A.x*B.y-B.x*A.y;
}
int ConvexHull(Point *p,int n,Point *ch)
{
sort(p,p+n);
int m=;
for (int i= ;i<n ;i++)
{
while (m> && dcmp(cross(ch[m-]-ch[m-] , p[i]-ch[m-]))<=) m--;
ch[m++]=p[i];
}
int k=m;
for (int i=n- ;i>= ;i--)
{
while (m>k && dcmp(cross(ch[m-]-ch[m-] , p[i]-ch[m-]))<=) m--;
ch[m++]=p[i];
}
ch[m++]=ch[];
if (n>) m--;
return m;
}
double dis(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
int n;
while (cin>>n,n)
{
for (int i= ;i<n ;i++)
scanf("%lf%lf",&an[i].x,&an[i].y);
if (n==) {printf("0.00\n");continue;}
else if (n==) {printf("%.2f\n",dis(an[],an[]));continue;}
Point bn[];
int m=ConvexHull(an,n,bn);
double sum=;
for (int i= ;i<m ;i++)
{
sum += dis(bn[i],bn[i+]);
}
printf("%.2f\n",sum);
}
return ;
}
上一篇:Maven 打包可运行 jar


下一篇:redis入门指南学习笔记