首页 > ACM题库 > HDU-杭电 > hdu 2215 Maple trees-凸包问题-[解题报告]C++
2014
01-04

hdu 2215 Maple trees-凸包问题-[解题报告]C++

Maple trees

问题描述 :

There are a lot of trees in HDU. Kiki want to surround all the trees with the minimal required length of the rope . As follow,

To make this problem more simple, consider all the trees are circles in a plate. The diameter of all the trees are the same (the diameter of a tree is 1 unit). Kiki can calculate the minimal length of the rope , because it’s so easy for this smart girl.
But we don’t have a rope to surround the trees. Instead, we only have some circle rings of different radius. Now I want to know the minimal required radius of the circle ring. And I don’t want to ask her this problem, because she is busy preparing for the examination.
As a smart ACMer, can you help me ?

输入:

The input contains one or more data sets. At first line of each input data set is number of trees in this data set n (1 <= n <= 100), it is followed by n coordinates of the trees. Each coordinate is a pair of integers, and each integer is in [-1000, 1000], it means the position of a tree’s center. Each pair is separated by blank.
Zero at line for number of trees terminates the input for your program.

输出:

The input contains one or more data sets. At first line of each input data set is number of trees in this data set n (1 <= n <= 100), it is followed by n coordinates of the trees. Each coordinate is a pair of integers, and each integer is in [-1000, 1000], it means the position of a tree’s center. Each pair is separated by blank.
Zero at line for number of trees terminates the input for your program.

样例输入:

2
1 0
-1 0
0

样例输出:

1.50

(思路明显错了)

最小覆盖圆必定是某三个顶点的外接圆。

先求凸包再枚举。

 

// hdu 2215.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "math.h"
#include <iostream>
using namespace std;
#define ABS_N(x) ((x)<0?-(x):(x))
int N,stack_top;
struct Node
{
	int x,y;
}m_stack[1005],position[1005];
inline int CrossMutiply(Node p1,Node p2,Node p3)
{
	return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
}
inline int Distance(Node p1,Node p2)
{
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
int CMP(const void* a,const void* b)
{
	Node *p1=(Node*)a,*p2=(Node*)b;
	int m=CrossMutiply(position[0],*p1,*p2);
	if(m==0) return Distance(position[0],*p1)-Distance(position[0],*p2);
	else return -m;
}
void Convex()
{
	int swap=0;
	for(int i=1;i<N;i++)
	{
		if((position[i].y<position[swap].y)||(position[i].y==position[swap].y&&position[i].x<position[swap].x))
			swap=i;
	}
	Node temp=position[swap];
	position[swap]=position[0];
	position[0]=temp;
	qsort(position+1,N-1,sizeof(position[0]),CMP);
	m_stack[0]=position[0];
	m_stack[1]=position[1];
	stack_top=1;
	for(int i=2;i<N;i++)
	{
		while(stack_top>=1&&CrossMutiply(m_stack[stack_top-1],m_stack[stack_top],position[i])<=0)
			stack_top--;
		m_stack[++stack_top]=position[i];
	}
}
inline double Diameter(Node p1,Node p2,Node p3)
{
	double temp=sqrt((double)Distance(p2,p3));
	double temp2=CrossMutiply(p1,p2,p3);
	temp2=temp2/(sqrt((double)(Distance(p1,p2)*Distance(p1,p3))));
	temp=temp/temp2;
	return ABS_N(temp);
}
int main()
{
	freopen("d://1.txt","r",stdin);
	double ans,temp;
	while(scanf("%d",&N)&&N)
	{
		for(int i=0;i<N;i++)
		{
			scanf("%d%d",&position[i].x,&position[i].y);
		}
		if(N==1)
		{
			printf("%.2f/n",0.5);
			continue;
		}
		else if(N==2)
		{
			printf("%.2f/n",sqrt((double)Distance(position[0],position[1]))/2+0.5);
			continue;
		}
		Convex();
		if(stack_top==1)
		{
			printf("%.2f/n",sqrt((double)Distance(m_stack[0],m_stack[1]))/2+0.5);
			continue;
		}
		ans=0;
		for(int i=0;i<stack_top-1;i++)
		{
			for(int j=i+1;j<stack_top;j++)
			{
				for(int k=j+1;k<=stack_top;k++)
				{
					temp=Diameter(m_stack[i],m_stack[j],m_stack[k]);
					if(temp>ans) ans=temp;
				}
			}
		}
		printf("%.2f/n",ans/2+0.5);
	}
	return 0;
}

解题转自:http://blog.csdn.net/logic_nut/article/details/4449976


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1