杭电4063题，求大牛指点。
题目链接：http://acm.hdu.这题测试修改了我整整一天，已经精疲力竭了，一直wronganswer，数据测试很多，和已经AC的代码的结果一样。可就是AC不了，明天上课了，没那么长时间折腾这个了，所以寻求大牛帮助。
之前没怎么做过ACM的题目，代码写的不是很好，望大牛不要见笑。还有大牛最好能指出错误，代码就别贴了。
我的思路是：先求出所有圆的交点，然后加上起始点、结束点组成一个节点集，然后找出所有可达的节点（可达指：两节点之间的线段都在圆中），求出两点间距离，作为边，组成图。然后用Dijkstra找出最短路。这是我的大概思路。下面是代码。
#include <iostream>
#include <math.h>
#include <vector>
#include <fstream>
#include <iomanip>
#include <map>
#include <algorithm>
using namespace std;
int T=1;
class Matirx
{
public:
int no;
double length;
};
class Point
{
public:
double x;
double y;
bool operator < (const Point a)const
{
return x<a.x||x==a.x&&y<a.y;
}
};
class Edge
{
public:
int no;
double length;
int lastno;
};
class Circle
{
public:
Point centrePoint;
double radius;
double radsqu;
};
int Mycount=0;
double precision=1e-8;
vector<Matirx> *matrix;
vector<Circle> circles;
vector<Point> point;
int countForPoint=0;
vector<Edge> getEdge;
int dblcmp(double x)
{
return fabs(x)<=precision?0:x>0?1:-1;
}
//求圆交点
int GetIntersectionPoint(Circle p0,Circle p1,Point *p)
{
Point p2Abs;
Point p2;
double t=0;
double hsquare=0;
double maxdistance=(p0.radius+p1.radius)*(p0.radius+p1.radius);
double dsquare=(p1.centrePoint.x-p0.centrePoint.x)*(p1.centrePoint.x-p0.centrePoint.x)+(p1.centrePoint.y-p0.centrePoint.y)*(p1.centrePoint.y-p0.centrePoint.y);
if (dblcmp(maxdistance-dsquare)<0)
{
return 0;
}
double temp=(dsquare+p0.radsqu-p1.radsqu)/(2*dsquare);
p2.x=(p1.centrePoint.x-p0.centrePoint.x)*temp+p0.centrePoint.x;
p2.y=(p1.centrePoint.y-p0.centrePoint.y)*temp+p0.centrePoint.y;
if (p2.x==0.0)
{
p[0].x=p0.radsqu-p2.y-p0.centrePoint.y*p2.y-p0.centrePoint.y;
p[0].y=p2.y;
p[1].x=-p[0].x;
p[1].y=p2.y;
}
else if (p2.y==0)
{
p[0].x=p2.x;
p[0].y=p0.radsqu-p2.x-p0.centrePoint.x*p2.x-p0.centrePoint.x;
p[1].x=p2.x;
p[1].y=-p[0].y;
}
else
{
hsquare=p0.radsqu-((dsquare*dsquare+p0.radsqu*p0.radsqu+p1.radsqu*p1.radsqu-2*p0.radsqu*p1.radsqu+2*p0.radsqu*dsquare-2*dsquare*p1.radsqu)/(4*dsquare));
if (abs(hsquare)<1e-15)
{
p[0].y=p2.y;
p[0].x=p2.x;
p[1].y=p2.y ;
p[1].x=p2.x;
}
else
{
p2Abs.x=p2.x-p0.centrePoint.x;
p2Abs.y=p2.y-p0.centrePoint.y;
t=sqrt((hsquare*pow(p2Abs.x,2))/(pow(p2Abs.y,2)+pow(p2Abs.x,2)));
p[0].y=p2.y + t;
p[0].x=(-(p2Abs.y*t)/p2Abs.x)+p2.x;
p[1].y=p2.y - t;
p[1].x=((p2Abs.y*t)/p2Abs.x)+p2.x;
}
}
return 1;
}
bool Fun(double a,double b,double c,double &x1,double &x2) //解一元二次方程
{
double t=b*b-4*a*c;
if(dblcmp(t)<0)return 0;
double tt=sqrt(t);
x1=(-b+tt)/(2*a);
x2=(-b-tt)/(2*a);
return 1;
}
void formal(Point p1,Point p2,double &a,double &b,double &c)
{
double x=p2.x-p1.x;
double y=p2.y-p1.y;
a=y;
b=-x;
c=p1.y*x-p1.x*y;
}
//判断线段所在直线是否进过圆
int IsLineCutCircle(Point a,Point b,Circle Y,Point& p1,Point& p2)
{
double A,B,C,t1,t2;
int zz=-1;
formal(a,b,A,B,C);
double d=fabs(A*Y.centrePoint.x+B*Y.centrePoint.y+C)/sqrt(A*A+B*B);
if(dblcmp(d-Y.radius)>0)return 0;
if(fabs(B)<1e-8)
{
p1.x=p2.x=-1.0*C/A;
zz=Fun(1.0,-2.0*Y.centrePoint.y,Y.centrePoint.y*Y.centrePoint.y
+(p1.x-Y.centrePoint.x)*(p1.x-Y.centrePoint.x)-Y.radsqu,t1,t2);
p1.y=t1;p2.y=t2;
}
else if(fabs(A)<1e-8)
{
p1.y=p2.y=-1.0*C/B;
zz=Fun(1.0,-2.0*Y.centrePoint.x,Y.centrePoint.x*Y.centrePoint.x
+(p1.y-Y.centrePoint.y)*(p1.y-Y.centrePoint.y)-Y.radsqu,t1,t2);
p1.x=t1;p2.x=t2;
}
else
{
zz=Fun(A*A+B*B,2.0*A*C+2.0*A*B*Y.centrePoint.y
-2.0*B*B*Y.centrePoint.x,B*B*Y.centrePoint.x*Y.centrePoint.x+C*C+2*B*C*Y.centrePoint.y
+B*B*Y.centrePoint.y*Y.centrePoint.y-B*B*Y.radsqu,t1,t2);
p1.x=t1,p1.y=-1*(A/B*t1+C/B);
p2.x=t2,p2.y=-1*(A/B*t2+C/B);
}
return 1;
}
//判断点是否在圆内
int IsPointInCircle(Circle cir,Point po)
{
double disSqu=(po.x-cir.centrePoint.x)*(po.x-cir.centrePoint.x)+(po.y-cir.centrePoint.y)*(po.y-cir.centrePoint.y);
double radiusSqu=cir.radsqu;
if (radiusSqu-disSqu>=-precision)
{
return 1;
}
else
return 0;
}
//判断点是否在线段之间
int IspointInline(Point p1,Point start,Point end)
{
double startx,starty,endx,endy;
if (start.x>end.x)
{
startx=start.x+precision;
endx=end.x-precision;
}
else
{
startx=end.x+precision;
endx=start.x-precision;
}
if(start.y>end.y)
{
starty=start.y+precision;
endy=end.y-precision;
}
else
{
starty=end.y+precision;
endy=start.y-precision;
}
if(p1.x<endx||p1.x>startx||p1.y<endy||p1.y>starty)
{
return 0;
}
else
{
return 1;
}
}
//最短路
int Dij()
{
int used[10000]={0};
int startPoint=0;
int getEdgeNo=0;
int endPoint=countForPoint;
getEdge.clear();
vector<Edge> freshEdge;
Edge edge;
edge.no=0;
edge.length=0;
edge.lastno=0;
getEdge.push_back(edge);
used[0]=1;
double min=0;
int noteNo=0;
int noteForGetCount=0;
int flag=0;
int templastno=0;
while(getEdgeNo!=countForPoint)
{
vector<Edge>::iterator it;
min=10000000;
noteNo=-1;
for(it=getEdge.begin();it!=getEdge.end();it++)
{
int tempNo=it->no;
vector<Matirx>::iterator it2;
for (it2=matrix[tempNo].begin();it2!=matrix[tempNo].end();it2++)
{
if (used[it2->no]==0)
{
if(min>(*it).length+it2->length)
{
min=(*it).length+it2->length;
noteNo=it2->no;
templastno=it->no;
}
}
}
}
if (noteNo==-1)
{
flag=1;
break;
}
used[noteNo]=1;
Edge edge;
edge.no=noteNo;
edge.length=min;
edge.lastno=templastno;
getEdgeNo=noteNo;
getEdge.push_back(edge);
}
if (flag==1)
{
return 0;
}
else
{
return 1;
}
}
double Distance(Point p1,Point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
Point fir;
bool comp(Point a,Point b)
{
return Distance(fir,a)<Distance(fir,b);
}
int IsLineInCircles(Point p1,Point p2,Point start,Point end)
{
for (int j=0;j<Mycount;j++)
{
if (IsPointInCircle(circles[j],p1)&&IsPointInCircle(circles[j],p2))
{
return 1;
}
}
return 0;
}
int IsLineOK(Point p1,Point p2)
{
int countForIntePoint=0;
fir=p1;
Point *set=new Point[2*Mycount];
for (int i=0;i<Mycount;i++)
{
Point temp1,temp2;
if (IsLineCutCircle(p1,p2,circles[i],temp1,temp2))
{
if (IspointInline(temp1,p1,p2))
{
set[countForIntePoint]=temp1;
countForIntePoint++;
}
if (IspointInline(temp2,p1,p2))
{
set[countForIntePoint]=temp2;
countForIntePoint++;
}
}
}
sort(set,set+countForIntePoint,comp);
for (int i=0;i<countForIntePoint-1;i++)
{
if (!IsLineInCircles(set[i],set[i+1],p1,p2))
{
delete []set;
return 0;
}
}
delete []set;
return 1;
}
void Add(Point temp,int &countFor)
{
for (int i=0 ;i<countFor;i++)
{
if (point[i].x==temp.x&&point[i].y==temp.y)
{
return ;
}
}
point.push_back(temp);
countFor++;
}
int main()
{
map<Point,int> hashs;
ifstream cin("Mit.txt");
int countForEdge=0;
int countForInter=0;
Point *tempPoint=new Point[2];
int total;
cin>>total;
/*cout.precision(5);*/
while(total>0)
{
countForPoint=1;
total--;
cin>>Mycount;
hashs.clear();
for (int i=0;i<Mycount;i++)
{
Circle ctemp;
cin>>ctemp.centrePoint.x>>ctemp.centrePoint.y>>ctemp.radius;
ctemp.radsqu=ctemp.radius*ctemp.radius;
circles.push_back(ctemp);
}
point.push_back(circles[0].centrePoint);
hashs[circles[0].centrePoint]=1;
//找出点
for(int i=0;i<Mycount;i++)
{
for (int j=i+1;j<Mycount;j++)
{
if(GetIntersectionPoint(circles[i],circles[j],tempPoint))
{
if (hashs[tempPoint[0]]==0)
{
point.push_back(tempPoint[0]);
hashs[tempPoint[0]]=1;
countForPoint++;
}
if (hashs[tempPoint[1]]==0)
{
point.push_back(tempPoint[1]);
hashs[tempPoint[1]]=1;
countForPoint++;
}
}
}
}
point.push_back(circles[Mycount-1].centrePoint);
matrix=new vector<Matirx>[countForPoint];
int k=0;
//生成图
for (int i=0;i<=countForPoint;i++)
{
for (int j=i+1;j<=countForPoint;j++)
{
if(IsLineOK(point[i],point[j]))
{
Matirx temp;
temp.no=j;
temp.length=Distance(point[i],point[j]);
matrix[i].push_back(temp);
/* cout<<k++<<endl;
cout<<"x:"<<point[i].x<<" y:"<<point[i].y<<" ";
cout<<"x:"<<point[j].x<<" y:"<<point[j].y<<endl;
cout<<"edge:"<<temp.length<<endl<<endl;*/
}
}
}
//Dijkstra最短路
if (Dij()==0)
{
printf("Case %d: No such path.\n",T++);
}
else
{
Edge e=getEdge[getEdge.size()-1];
printf("Case %d: %.4lf\n",T++,e.length);
/*int cur=countForPoint;
while( cur!=0)
{
vector<Edge>::iterator it;
for(it=getEdge.begin();it!=getEdge.end();it++)
{
if (it->no==cur)
{
cout<<cur<<" ";
cur=it->lastno;
}
}*/
//}
}
point.clear();
circles.clear();
}
system("pause");
}
