hdu 4063 Aircraft 计算几何+最短路-白红宇

hdu 4063 Aircraft 计算几何+最短路

阅读量：4582 次

发布时间：2019-06-09

本文共 3585 字，大约阅读时间需要 11 分钟。

易知最短路一定是以圆心或者两圆交点作为中间点到达的。所以把这些点拿出来建图跑最短路就够了。

如今的问题就是，给定两个点，是否能连边 add(a,b,dist(a,b))

题目要求，ab线段必须全然在圆上，所以能够求出ab线段和全部圆的全部交点，对于随意相邻两个交点，它们必处于同一个圆内，否则不可达。点的编号用map就够了（一開始我以为double有精度问题无法map。用两个longlong保存然后乘上1000000000，后来发现没问题。应该是这题都是整点，精度要求不高的原因吧）

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            using namespace std;#define pi acos(-1.0)#define eps 1e-10int cmp(double x){ if(fabs(x)
            
             0) return 1; return -1;}double sqr(double x){ return x*x;}struct point{ double x,y; point(){}; point(double a,double b):x(a),y(b){}; void out() { printf("%lf %lf\n",x,y); } void input() { scanf("%lf%lf",&x,&y); } friend point operator +(const point &a,const point &b) { return point(a.x+b.x,a.y+b.y); } friend point operator -(const point &a,const point &b) { return point(a.x-b.x,a.y-b.y); } friend bool operator ==(const point &a,const point &b) { return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0; } bool operator <(const point &a) const { if(x==a.x) return y
             
               crosspoint(point ap,double ar,point bp,double br){ double d=(ap-bp).norm(); double cost = (ar*ar + d*d -br*br)/(2*ar*d); double sint=sqrt(1.0-cost*cost); point v=(bp-ap)/(bp-ap).norm()*ar; return make_pair(ap+rotate(v,cost,-sint),ap+rotate(v,cost,sint));}void circle_cross_line(point a,point b,point o,double r,point ret[],int &num) { double x0 = o.x ,y0 = o.y; double x1 = a.x, y1 = a.y; double x2 = b.x, y2 = b.y; double dx = x2-x1, dy = y2-y1; double A = dx*dx+dy*dy; double B = 2*dx*(x1-x0) + 2*dy*(y1-y0); double C = sqr(x1-x0) + sqr(y1-y0)-sqr(r); double delta = B*B-4*A*C; if( cmp(delta) >= 0) { double t1 = (-B - sqrt(delta)) / (2*A); double t2 = (-B + sqrt(delta)) / (2*A); if(cmp(t1-1)<=0 && cmp(t1)>=0) ret[num++] = point(x1+t1*dx,y1+t1*dy); if(cmp(t2-1) <=0 && cmp(t2)>=0) ret[num++] = point(x1+t2*dx,y1+t2*dy); }}struct rad{ point c; double r;}ra[300];int n;map
              
                mp;int ID;int que[123456];point xx[100005];struct node2{ int v,next; double w;}e[123456];int head[12345];bool in[12345];double d[12345];int en;void add(int a,int b,double c){ // printf("%d %d %lf\n",a,b,c); e[en].v=b; e[en].w=c; e[en].next=head[a]; head[a]=en++; e[en].v=a; e[en].w=c; e[en].next=head[b]; head[b]=en++;}void spfa(int st){ queue
               
                 q; memset(in,0,sizeof(in)); for(int i=1;i<=ID;i++) d[i]=1000000000; q.push(st); in[st]=1; d[st]=0; int tmp; while(!q.empty()) { tmp=q.front();q.pop(); in[tmp]=0; for(int i=head[tmp];~i;i=e[i].next) { if(d[e[i].v]>d[tmp]+e[i].w) { d[e[i].v]=d[tmp]+e[i].w; if(!in[e[i].v]) { in[e[i].v]=1; q.push(e[i].v); } } } }}bool inra(point &x,point &y){ for(int i=1;i<=n;i++) { if(dist(x,ra[i].c)<=ra[i].r+eps && dist(y,ra[i].c)<=ra[i].r+eps) { return true; } } return false;}point my[12345];bool cal(point &a,point &b){ my[0]=a; int top=1; for(int i=1;i<=n;i++) { circle_cross_line(a,b,ra[i].c,ra[i].r,my,top); } my[top++]=b; sort(my,my+top); for(int i=1;i
                
                 (ra[i].r+ra[j].r)+0.0) continue; pair
                 
                   tmp=crosspoint(ra[i].c,ra[i].r,ra[j].c,ra[j].r); if(mp[tmp.first]==0) { mp[tmp.first]=++ID; que[top++]=ID; xx[ID]=tmp.first; } if(mp[tmp.second]==0) { mp[tmp.second]=++ID; que[top++]=ID; xx[ID]=tmp.second; } } } mp[ra[n].c]=++ID; que[top++]=ID; xx[ID]=ra[n].c; for(int i=0;i
                  
                   =1000000000) puts("No such path."); else printf("%.4f\n",d[ID]); } return 0;}/*9920 0 12 0 120 0 14 1 24-4 0 1-1 0 21 0 24 0 13-3 0 10 0 20 3 13-3 0 10 0 2-2 -1 13-3 0 1-2 -1 10 0 242 2 22 -2 2-2 2 2-2 -2 220 0 31 0 130 0 12 2 23 0 130 0 13 0 12 2 2ans:2.0000No8.00004.82841.41423.00006.82841.00003.06542.8284*/

转载于:https://www.cnblogs.com/yxwkf/p/5073123.html

你可能感兴趣的文章