2015
04-16

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

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


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.