HDU 1392 Surround the Trees

本文由 Ocrosoft 于 2017-06-28 16:10:40 发表

Surround the Trees

Time
Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 11188    Accepted Submission(s):
4347

Problem Description
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.

There are no more than 100
trees.
 

Input
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.
 

Output
The minimal length of the rope. The precision should be
10^-2.
 

Sample Input
	
9 12 7 24 9 30 5 41 9 80 7 50 87 22 9 45 1 50 7 0
 

Sample Output
	
243.06
 

Solution

题意:一个凸包把所有点包起来。

思路:略。两个点的时候只计算一条线的距离。

 

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <map>
#include <cmath>
#include <climits>
using namespace std;
struct point
{
	int x,y;
};
const int MAXN=120;
point list[MAXN];
int stack[MAXN],top;

int cross(point p0,point p1,point p2) //计算叉积  p0p1 X p0p2 
{
	return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}    
double dis(point p1,point p2)  //计算 p1p2的 距离 
{
	return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}    
bool cmp(point p1,point p2) //极角排序函数 , 角度相同则距离小的在前面 
{
	int tmp=cross(list[0],p1,p2);
	if(tmp>0) return true;
	else if(tmp==0&&dis(list[0],p1)<dis(list[0],p2)) return true;
	else return false;
}    
void init(int n) //输入,并把  最左下方的点放在 list[0]  。并且进行极角排序 
{
	int i,k;
	point p0;
	scanf("%d%d",&list[0].x,&list[0].y);
	p0.x=list[0].x;
	p0.y=list[0].y;
	k=0;
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&list[i].x,&list[i].y);
		if( (p0.y>list[i].y) || ((p0.y==list[i].y)&&(p0.x>list[i].x)) )
		{
			p0.x=list[i].x;
			p0.y=list[i].y;
			k=i;
		}    
	}    
	list[k]=list[0];
	list[0]=p0;

	sort(list+1,list+n,cmp);
}     

void graham(int n)
{
	int i;
	if(n==1) {top=0;stack[0]=0;}
	if(n==2)
	{
		top=1;
		stack[0]=0;
		stack[1]=1;
	}    
	if(n>2)
	{
		for(i=0;i<=1;i++) stack[i]=i;
		top=1;

		for(i=2;i<n;i++)
		{
			while(top>0&&cross(list[stack[top-1]],list[stack[top]],list[i])<=0) top--;
			top++;
			stack[top]=i;
		}    
	}    
}    

int main()
{
	int n;
	while(cin>>n && n)
	{
		init(n);
		graham(n);
		double ans=0;
		for(int i=0;i<top;i++)
			ans+=dis(list[stack[i]],list[stack[i+1]]);
		if(n!=2)ans+=dis(list[stack[top]],list[stack[0]]);
		printf("%.2lf\n",ans);
	}
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » HDU 1392 Surround the Trees

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址