2014
01-04

# 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;
}

1. 斗破苍穹这部漫画，除了更新死慢死慢，看的时候出黄色，每到精彩的地方就不更了，让我们学会了耐心，使我们明白，还是先看小说吧。

2. 在方法1里面：

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

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

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