| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 478 人关注过本帖
标题:杭电4063题,求大牛指点。
只看楼主 加入收藏
Mitisky
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2012-10-7
结帖率:0
收藏
已结贴  问题点数:20 回复次数:3 
杭电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");

}
搜索更多相关主题的帖子: 最好 
2012-10-07 23:05
遗矢的老人
Rank: 9Rank: 9Rank: 9
来 自:成都
等 级:蜘蛛侠
威 望:7
帖 子:325
专家分:1131
注 册:2012-7-20
收藏
得分:7 
顶下
2012-10-08 21:13
天机阁主
Rank: 2
等 级:论坛游民
帖 子:4
专家分:11
注 册:2012-10-8
收藏
得分:7 
代码太长了 看的眼睛都花了
2012-10-08 22:58
xtjopt
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:89
专家分:168
注 册:2012-9-12
收藏
得分:7 
顶下
2012-10-09 11:10
快速回复:杭电4063题,求大牛指点。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.022924 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved