首页 > ACM题库 > HDU-杭电 > HDU 4063-Aircraft-最短路径-[解题报告]HOJ
2015
04-16

HDU 4063-Aircraft-最短路径-[解题报告]HOJ

Aircraft

问题描述 :

You are playing a flying game.
In the game, player controls an aircraft in a 2D-space.
The mission is to drive the craft from starting point to terminal point.
The craft needs wireless signal to move.
A number of devices are placed in the 2D-space, spreading signal.
For a device Di, it has a signal radius — Ri.
When the distance between the craft and Di is shorter or equal to Ri, it(the craft) gets Di’s wireless signal.
Now you need to tell me the shortest path from starting point to terminal point.

输入:

The first line of the input file is a single integer T.
The rest of the test file contains T blocks.
Each block starts with an integer n, followed by n devices given as (xi, yi, Ri).
(xi, yi) is position of Di, and Ri is the radius of its signal range.
The first point is the starting point.
The last point is the terminal point.
T <= 25;
2 <= n <= 20 for most cases;
20 < n <= 25 for several cases, completely random generated.
-1000 <= xi, yi <= 1000 , 1 <= ri <= 1000.
All are integers.

输出:

The first line of the input file is a single integer T.
The rest of the test file contains T blocks.
Each block starts with an integer n, followed by n devices given as (xi, yi, Ri).
(xi, yi) is position of Di, and Ri is the radius of its signal range.
The first point is the starting point.
The last point is the terminal point.
T <= 25;
2 <= n <= 20 for most cases;
20 < n <= 25 for several cases, completely random generated.
-1000 <= xi, yi <= 1000 , 1 <= ri <= 1000.
All are integers.

样例输入:

2
2
0 0 1
2 0 1
2
0 0 1
4 1 2

样例输出:

Case 1: 2.0000
Case 2: No such path.

相信在比赛的时候看这题的大家,都很无语吧~~!!

我是卡了整场了。。。中途看了其他题几眼,又回来这题了。。。

我第一个就是看的这个题(因为题目短,而且看着比较顺眼。。。)。。。然后就走向了一条不归路。。。泪。。。

第一反应,这不是裸的最短路么,很快敲了个,直接用floyd了,比较懒,顺利WA。。

然后想到了,可以不经过圆心的,那不就是经过交点喽???

然后套模板,圆相交模板。。。算出来交点,然后建图。。。用SPFA。。。顺利WA。。。

后来回来看这个题,想到了,如下图这个trick,谈不上trick吧,就是完全可以不经过任何交点到达另外一个点。这么一来,任意两个交点(包括圆心,以及俩圆的交点)都可能存在这样的路。

判断是个问题,后来小白说,可以一段一段判断,想了下,不难实现,就写了。。。结果WA了。。。结果比赛结束这题还是没能过。。。

后来找大牛要了几组数据,发现有个小于等于写成小于了,改了后,就A掉了。。

其中这个判断线段是否完全被圆形覆盖应该是比较困扰的,可以求出线段与圆所有交点,然后对这些交点排序,然后判断相邻俩点之间的线段是否被一个圆覆盖,这个的话可以判断这俩交点之间的中点是否被一个圆覆盖。

总体的时间复杂度应该是N^5。。到N^6之间。。

Aircraft

#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen(x, "r", stdin)
#define file_w(x) freopen(x, "w", stdout)

using namespace std;

const int MAX = 1000;
const double eps = 1e-6;
const double inf = 1e50;
struct point{
	double x, y;
	void get()
	{
		scanf("%lf%lf", &x, &y);
	}
};
bool dy(double x,double y)	{	return x > y + eps;}	// x > y 
bool xy(double x,double y)	{	return x < y - eps;}	// x < y 
bool dyd(double x,double y)	{ 	return x > y - eps;}	// x >= y 
bool xyd(double x,double y)	{	return x < y + eps;} 	// x <= y 
bool dd(double x,double y) 	{	return fabs( x - y ) < eps;}  // x == y
double disp2p(point a,point b) //  a b 两点之间的距离 
{
	return sqrt( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) );
}
bool operator==(point a, point b)
{
	return dd(a.x, b.x) && dd(a.y, b.y);
}

typedef struct NODE{
	int to;
	double len;
	NODE *next;
}NODE;
NODE *p[MAX],node[MAX*MAX];
struct circle{
	point c;
	double r;
};
circle c[MAX];
int cou;
void init()
{
	cou = 0;
	memset(p, 0, sizeof(p));
}
void Add(int from,int to,double len)
{
	node[cou].next = p[from];
	node[cou].to = to;
	node[cou].len = len;
	p[from] = &node[cou++];
}
queue<int> q;
double SPFA_List(int from,int to,int n)
{
	while( !q.empty() ) q.pop();
	double dis[MAX];
	bool inq[MAX];
	for(int i=0; i<n; i++)
		dis[i] = inf;
	memset(inq,false,sizeof(inq));
	dis[from] = 0;
	q.push(from);
	inq[from] = 1;
	while( !q.empty() )
	{
		int now = q.front();
		q.pop();
		inq[now] = false;
		NODE *head = p[now];
		while( head != NULL )
		{
			int v = head->to;
			double len = head->len;
			if( dy(dis[v], dis[now] + len) )
			{
				dis[v] = dis[now] + len;
				if( !inq[v] )
				{
					inq[v] = true;
					q.push(v);
				}
			}
			head = head->next;
		}
	}
	if( dd(dis[to], inf) ) return -1;
	return dis[to];
}

point l2l_inst_p(point u1,point u2,point v1,point v2)
{
	point ans = u1;
	double t = ((u1.x - v1.x)*(v1.y - v2.y) - (u1.y - v1.y)*(v1.x - v2.x))/
				((u1.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x));
	ans.x += (u2.x - u1.x)*t;
	ans.y += (u2.y - u1.y)*t;
	return ans;
}
void l2c_inst_p(point c,double r,point l1,point l2,point &p1,point &p2)
{
	point p = c;
	double t;
	p.x += l1.y - l2.y;
	p.y += l2.x - l1.x;
	p = l2l_inst_p(p,c,l1,l2);
	t = sqrt(r*r - disp2p(p,c)*disp2p(p,c))/disp2p(l1,l2);
	p1.x = p.x + (l2.x - l1.x)*t;
	p1.y = p.y + (l2.y - l1.y)*t;
	p2.x = p.x - (l2.x - l1.x)*t;
	p2.y = p.y - (l2.y - l1.y)*t;
}
void c2c_inst_p(point c1,double r1,point c2,double r2,point &p1,point &p2)
{
	point u,v;
	double t;
	t = (1 + (r1*r1 - r2*r2)/disp2p(c1,c2)/disp2p(c1,c2))/2;
	u.x = c1.x + (c2.x - c1.x)*t;
	u.y = c1.y + (c2.y - c1.y)*t;
	v.x = u.x + c1.y - c2.y;
	v.y = u.y - c1.x + c2.x;
	l2c_inst_p(c1,r1,u,v,p1,p2);
}
bool c2c_tangent(point a,double r1,point b,double r2)
{
	if( dd(disp2p(a,b),r1+r2) || dd(disp2p(a,b),fabs(r1-r2)) )
		return true;
	return false;
}
point c2c_tangent_p(point a,double r1,point b,double r2)
{
	point t;
	if( dd(disp2p(a,b),r1 + r2)  )
	{
		t.x = (r1*b.x + r2*a.x)/(r1 + r2);
		t.y = (r1*b.y + r2*a.y)/(r1 + r2);
		return t;
	}
	t.x = (r1*b.x - r2*a.x)/(r1 - r2);
	t.y = (r1*b.y - r2*a.y)/(r1 - r2);
	return t;
}
point g[MAX];
bool f[MAX][MAX];
double crossProduct(point a,point b,point c)//向量 ac 在 ab 的方向 顺时针是正 
{
	return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);
}
double disp2l(point a,point l1,point l2)
{
	return fabs( crossProduct(a,l1,l2) )/disp2p(l1,l2);
}
bool onSegment(point a, point b, point c)
{
	if( dd(crossProduct(a,b,c),0.0) && dyd(c.x,min(a.x,b.x)) && 
		xyd(c.x,max(a.x,b.x)) && dyd(c.y,min(a.y,b.y)) && xyd(c.y,max(a.y,b.y)) )
		return true;
	return false;
}
bool cmp(point a, point b)
{
	if( dd(a.x, b.x) )	return xy(a.y, b.y);
	return xy(a.x, b.x);
}
point tp[MAX];
bool check(int cnt, int n)
{
	FOR(i, 1, cnt)
	{
		point tt;
		tt.x = (tp[i].x + tp[i-1].x)/2;
		tt.y = (tp[i].y + tp[i-1].y)/2;
		bool f = false;
		FOR(k, 0, n)
			if( xyd(disp2p(c[k].c, tt), c[k].r) )
			{
				f = true;
				break;
			}
		if( !f )
			return false;
	}
	return true;
}
double solve(int n)
{
	int l = 0;
	int s = 0, t = n-1;
	FOR(i, 0, n)
		g[l++] = c[i].c;
		
	FOR(i, 0, n)
	{
		FOR(k, i+1, n)
		{
			if( dy(disp2p(c[i].c, c[k].c), c[i].r + c[k].r) 
					|| c[i].c == c[k].c )
				continue;
			if( c2c_tangent(c[i].c, c[i].r, c[k].c, c[k].r) )
			{
				point tt = c2c_tangent_p(c[i].c, c[i].r, c[k].c, c[k].r);
				g[l++] = tt;
				continue;
			}
			point t1, t2;
			c2c_inst_p(c[i].c, c[i].r, c[k].c, c[k].r, t1, t2);
			g[l++] = t1;
			g[l++] = t2;
		}
	}
	memset(f, false, sizeof(f));
	int tmp[MAX];
	FOR(i, 0, n)
	{
		int cnt = 0;
		FOR(k, 0, l)
			if( xyd(disp2p(c[i].c, g[k]), c[i].r) )
				tmp[cnt++] = k;
		FOR(k, 0, cnt)
			FOR(j, k+1, cnt)
			{
				int x = tmp[k], y = tmp[j];
				if( f[x][y] ) continue;
				double dis = disp2p(g[x], g[y]);
				Add(x, y, dis);
				Add(y, x, dis);
				f[x][y] = f[y][x] = true;
			}		
	}
	FOR(i, 0, l)
		FOR(k, i+1, l)
		{
			if( f[i][k] ) continue;
			int cnt = 0;
			tp[cnt++] = g[i];
			tp[cnt++] = g[k];
			FOR(j, 0, n)
				if( xyd(disp2l(c[j].c, g[i], g[k]),c[j].r) )
				{
					point t1, t2;
					l2c_inst_p(c[j].c, c[j].r, g[i], g[k], t1, t2);
					if( onSegment(g[i], g[k], t1) )
						tp[cnt++] = t1;
					if( onSegment(g[i], g[k], t2) )
						tp[cnt++] = t2;		
				}
			sort(tp, tp+cnt, cmp);
			if( check(cnt, n) )
			{
				Add(i, k, disp2p(g[i], g[k]));
				Add(k, i, disp2p(g[k], g[i]));
			}
		}
	return SPFA_List(s, t, l);
}

int main()
{
	int ncases, n, ind = 1;
	
	scanf("%d", &ncases);
	
	while( ncases-- )
	{
		scanf("%d", &n);
		init();
		FOR(i, 0, n)
		{
			c[i].c.get();
			scanf("%lf", &c[i].r);
		}
		
		double ans = solve(n);
		printf("Case %d: ",ind++);
		if( ans < -eps )
			puts("No such path.");
		else
			printf("%.4lf\n", ans);
	}

return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/zxy_snow/article/details/6849550


  1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  2. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  4. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.