首页 > ACM题库 > HDU-杭电 > hdu 2273 The buses[解题报告]c-sharp
2014
01-04

hdu 2273 The buses[解题报告]c-sharp

The buses

问题描述 :

Garfield applied for a good job recently, and he will go to work soon by car or bus. Garfield is very broody, sometimes when he sits on the bus to wait for the traffic light, he thinks about how long all the buses pass the traffic turning.
  Now we describe the situations when the buses stop at the traffic turning to wait for the traffic light. First the light is red, then when the light changes to green, all the buses are prepared to move. And at the beginning, all the buses are close to each other without any space, and they have different lengths and the largest speeds. We assume any car can reach the speed that isn’t beyond the maximal speed at once.
  Now Garfield wants you to calculate minimal time all the buses pass the turning.

输入:

There are many cases. For each case, there is two intergers N(1<=N<=100), representing the number of the buses. There are two interges in the following N lines, for the length Li(meter, 1<=Li<=10) and the maximal speed Si(meter/second, 1<=Si<=10) of the i-th bus.

输出:

There are many cases. For each case, there is two intergers N(1<=N<=100), representing the number of the buses. There are two interges in the following N lines, for the length Li(meter, 1<=Li<=10) and the maximal speed Si(meter/second, 1<=Si<=10) of the i-th bus.

样例输入:

2
1 2
2 3

样例输出:

1.50

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2773

 

题意:给出内外两个不相交多边形,求出能通过这两个多边形之间的最大的圆半径.

 

题目分析:点的数量非常少,100个点,完全可以求出所有的两多边形上的点分别到

             另外一个多边形线段的所有的最短距离.

 

  刚开始一直WA,竟然想当然的

认为所求的结果是内部多边形点到外部多边形边的最短距离…

3824185 2011-04-15 21:32:18 Accepted 2773 15MS 240K 1360 B C++ ㄉ ㄉ

#include<stdio.h>
#include<string.h>
#include<math.h>
const double eps = 1e-9;
const double f=10e10;
#define M 108
typedef struct{
	double x,y;
}Point;
Point inner[M],outer[M];
int oi,oo;
double Dis(Point p,Point q)
{
	return (p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y);
}
double Multi(Point p,Point q,Point o)
{
	return (p.x-o.x)*(q.y-o.y)-(q.x-o.x)*(p.y-o.y);
}
double DotMulti(Point p,Point q,Point o)
{
	return (p.x-o.x)*(q.x-o.x)+(p.y-o.y)*(q.y-o.y);
}
double Fix(Point o,Point p,Point q)
{
	double ret,tmp,area;
	ret=Dis(o,p);
	tmp=Dis(o,q);
	if(tmp<ret) ret=tmp;
	
	if((DotMulti(o,q,p)<eps||DotMulti(o,p,q)<eps))
		return ret;
	
	area=fabs(Multi(o,p,q));
	
	tmp=(area/sqrt(Dis(p,q)));
	tmp*=tmp;
	if(tmp<ret) ret=tmp;
	return ret;
}
int main()
{
	int t,i,j;
	double tmp,ans;
	scanf("%d",&t);
	
	while(t--){
		scanf("%d",&oi);
		for(i=0;i<oi;i++)
			scanf("%lf%lf",&inner[i].x,&inner[i].y);
		scanf("%d",&oo);
		for(i=0;i<oo;i++)
			scanf("%lf%lf",&outer[i].x,&outer[i].y);
		inner[oi]=inner[0];
		outer[oo]=outer[0];
		ans=f;
		for(i=0;i<oi;i++){
			for(j=0;j<oo;j++){
				tmp=Fix(outer[j],inner[i],inner[i+1]);
				if(tmp<ans) ans=tmp;
				tmp=Fix(inner[i],outer[j],outer[j+1]);
				if(tmp<ans)	ans=tmp;
				
			}
		}
		printf("%f/n",sqrt(ans)*0.5000);
	}
	return 0;
}

 

解题转自:http://blog.csdn.net/dooder_daodao/article/details/6326692


  1. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  2. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧