Aircraft

Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 1244 Accepted Submission(s): 304

Problem Description

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.

Input

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.

Output

For each case, Output "No such path." if the craft can't get to the terminal point.

Otherwise, output a float number, correct the result to 4 decimal places.(as shown in the sample output)

Sample Input

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

Sample Output

Case 1: 2.0000 Case 2: No such path.

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define MAX_N 110/*------------------常量区-------------------*/const double INF = 1e10; // 无穷大const double EPS = 1e-8; // 计算精度const double PI = acos(-1.0);// PIconst int PINXING = 0; // 平行const int XIANGJIAO = 1; // 相交const int XIANGLI = 0; // 相离const int GONGXIAN = 2; // 共线const int CHONGDIE = -1; // 重叠const int INSIDE = 1; // 点在图形内部const int OUTSIDE = 0; // 点在图形外部const int BORDER = 2; // 点在图形边界/*-----------------类型定义区----------------*/struct Point { // 二维点或矢量 double x, y; //double angle, dis; Point() {} Point(double x0, double y0): x(x0), y(y0) {} void read() { scanf("%lf%lf",&x,&y); }};struct Point3D { //三维点或矢量 double x, y, z; Point3D() {} Point3D(double x0, double y0, double z0): x(x0), y(y0), z(z0) {}};struct Line { // 二维的直线或线段 Point p1, p2; Line() {} Line(Point p10, Point p20): p1(p10), p2(p20) {} void read() { scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y); }};struct Line3D { // 三维的直线或线段 Point3D p1, p2; Line3D() {} Line3D(Point3D p10, Point3D p20): p1(p10), p2(p20) {}};struct Rect { // 用长宽表示矩形的方法 w, h分别表示宽度和高度 double w, h; Rect() {} Rect(double _w,double _h) : w(_w),h(_h) {}};struct Rect_2 { // 表示矩形，左下角坐标是(xl, yl)，右上角坐标是(xh, yh) double xl, yl, xh, yh; Rect_2() {} Rect_2(double _xl,double _yl,double _xh,double _yh) : xl(_xl),yl(_yl),xh(_xh),yh(_yh) {}};struct Circle { //圆 Point c; double r; Circle() {} Circle(Point _c,double _r) :c(_c),r(_r) {}};typedef vector
            
              Polygon; // 二维多边形typedef vector
             
               Points; // 二维点集/*-------------------基本函数区---------------------*/inline double max(double x,double y){ return x > y ? x : y;}inline double min(double x, double y){ return x > y ? y : x;}inline bool ZERO(double x) // x == 0{ return (fabs(x) < EPS);}inline bool ZERO(Point p) // p == 0{ return (ZERO(p.x) && ZERO(p.y));}inline bool ZERO(Point3D p) // p == 0{ return (ZERO(p.x) && ZERO(p.y) && ZERO(p.z));}inline bool EQ(double x, double y) // eqaul, x == y{ return (fabs(x - y) < EPS);}inline bool NEQ(double x, double y) // not equal, x != y{ return (fabs(x - y) >= EPS);}inline bool LT(double x, double y) // less than, x < y{ return ( NEQ(x, y) && (x < y) );}inline bool GT(double x, double y) // greater than, x > y{ return ( NEQ(x, y) && (x > y) );}inline bool LEQ(double x, double y) // less equal, x <= y{ return ( EQ(x, y) || (x < y) );}inline bool GEQ(double x, double y) // greater equal, x >= y{ return ( EQ(x, y) || (x > y) );}// 输出浮点数前，防止输出-0.00调用该函数进行修正！inline double FIX(double x){ return (fabs(x) < EPS) ? 0 : x;}/*------------------二维矢量运算重载区---------------------*/bool operator==(Point p1, Point p2){ return ( EQ(p1.x, p2.x) && EQ(p1.y, p2.y) );}bool operator!=(Point p1, Point p2){ return ( NEQ(p1.x, p2.x) || NEQ(p1.y, p2.y) );}bool operator<(Point p1, Point p2){ if (NEQ(p1.x, p2.x)) { return (p1.x < p2.x); } else { return (p1.y < p2.y); }}Point operator+(Point p1, Point p2){ return Point(p1.x + p2.x, p1.y + p2.y);}Point operator-(Point p1, Point p2){ return Point(p1.x - p2.x, p1.y - p2.y);}double operator*(Point p1, Point p2) // 计算叉乘 p1 × p2{ return (p1.x * p2.y - p2.x * p1.y);}double operator&(Point p1, Point p2) { // 计算点积 p1·p2 return (p1.x * p2.x + p1.y * p2.y);}double Norm(Point p) // 计算矢量p的模{ return sqrt(p.x * p.x + p.y * p.y);}/*-------------------基本函数区------------------*///得到两点之间的距离double Dis(Point p1,Point p2){ return sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) );}//求二维平面上点到直线的距离double Dis(Point p, Line L){ return ( fabs((p - L.p1) * (L.p2 - L.p1)) / Norm(L.p2 - L.p1) );}//得到两点之间距离的平方，为减少误差用double Dis2(Point p1,Point p2){ return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);}// 把矢量p旋转角度angle (弧度表示)// angle > 0表示逆时针旋转// angle < 0表示顺时针旋转Point Rotate(Point p, double angle){ Point result; result.x = p.x * cos(angle) - p.y * sin(angle); result.y = p.x * sin(angle) + p.y * cos(angle); return result;}//得到向量p与x正半轴的夹角[0,2PI)double GetAngle(Point p){ double tmp=atan2(p.y,p.x); if(tmp<0) tmp=2*PI+tmp; return tmp;}//得到两个向量之间的夹角[0,PI]//若p1按顺时针转到p2的角小于PI(p1在p2的逆时针方向)，则返回正数.否则返回负数.double GetAngle(Point p1,Point p2){ double tmp = GetAngle(p1) - GetAngle(p2); if( GT( tmp,PI) ) return -(2*PI-tmp); if( LEQ( tmp,-PI) ) return (tmp+2*PI); return tmp;}// 判断二维平面上点是否在线段上// 输入：任意点p，和任意直线L// 输出：p在线段上返回1，否则返回0bool OnSeg(Point p, Line L){ return ( ZERO( (L.p1 - p) * (L.p2 - p) ) && LEQ((p.x - L.p1.x)*(p.x - L.p2.x), 0) && LEQ((p.y - L.p1.y)*(p.y - L.p2.y), 0) );}// 判断二维平面上点p是否在直线L上,在线段上返回1,否则返回0bool OnLine(Point p, Line L){ return ZERO( (p - L.p1) * (L.p2 - L.p1) );}bool OnCir(Point p,Circle cir){ return EQ( (p.x-cir.c.x)*(p.x-cir.c.x)+(p.y-cir.c.y)*(p.y-cir.c.y),cir.r*cir.r );}//得到点p到直线L的距离，并返回p到直直线L的最近点repdouble PtoLine(Point p,Line L,Point& rep){ if(L.p1==L.p2) { rep=L.p1; return Dis(p,L.p1); } Point a,b; a = L.p2-L.p1; b = p-L.p1; double dis12 = Dis(L.p1,L.p2); double dis = ( fabs(a*b) )/dis12; double k = (a&b)/(Norm(a)*dis12) ; rep.x = L.p1.x + k*(L.p2.x-L.p1.x); rep.y = L.p1.y + k*(L.p2.y-L.p1.y); return dis;}//得到点P到线段L的距离，并放回p到线段L的最近点repdouble PointToSeg(Point P, Line L,Point& rep){ if(L.p1 == L.p2) { rep = L.p1; return Dis(rep,P);//如果线段是一个点，返回这个点。 } Point result; double a, b, t; a = L.p2.x - L.p1.x; b = L.p2.y - L.p1.y; t = ( (P.x - L.p1.x) * a + (P.y - L.p1.y) * b ) / (a * a + b * b);//线段上的投影 if ( GEQ(t, 0) && LEQ(t, 1) ) { result.x = L.p1.x + a * t;//值得学习的由比例求坐标的方法。 result.y = L.p1.y + b * t; } else { if ( Norm(P - L.p1) < Norm(P - L.p2) ) { result = L.p1; } else { result = L.p2; } } return Dis(result, P);}/*-------------------几何题面积计算（注意正负!）----------------------*/// 根据三个顶点坐标计算三角形面积// 面积的正负按照右手旋规则确定,向量AB->向量ACdouble Area(Point A, Point B, Point C){ return ((B-A)*(C-A) / 2.0);}// 根据三条边长计算三角形面积double Area(double a, double b, double c){ double s = (a + b + c) / 2.0; return sqrt(s * (s - a) * (s - b) * (s - c));}//求圆的面积double Area(Circle C){ return PI * C.r * C.r;}// 计算多边形面积,复杂度:O(顶点数)// 面积的正负按照右手旋规则确定，顺时针为负double Area(Polygon _poly){ int nsize=_poly.size(); double area=0; for(int i=0;i
              
                INF-1 ) { return -1; } if(saveid==t) return mi; mark[saveid] = 1; for(int i=0;i
               
                 dis[saveid]+mat[saveid][i] ) { dis[i] = dis[saveid]+mat[saveid][i]; } } return -1;}int main() { int T; cin>>T; int tt=1; while(T--) { int n; scanf("%d",&n); for(int i=0;i
                
                 0)//有交点 { for(int k=0;k
                 
                  dis2) swap(dis1,dis2); ls[ lcnt ].l=dis1; ls[ lcnt ].r=dis2; lcnt++; } } } // 得出线段与所有圆，所交线段。 sort(ls,ls+lcnt,cmp); double pre=0; int sign=0; for(int k=0;k