大家好,又见面了,我是全栈君。
易知最短路一定是以圆心或者两圆交点作为中间点到达的。所以把这些点拿出来建图跑最短路就够了。
如今的问题就是,给定两个点,是否能连边 add(a,b,dist(a,b))
题目要求,ab线段必须全然在圆上,所以能够求出ab线段和全部圆的全部交点,对于随意相邻两个交点,它们必处于同一个圆内,否则不可达。点的编号用map就够了(一開始我以为double有精度问题无法map。用两个longlong保存然后乘上1000000000,后来发现没问题。应该是这题都是整点,精度要求不高的原因吧)
#include <cstdio> #include <iostream> #include <algorithm> #include <queue> #include <map> #include <cmath> #include <cstring> using namespace std; #define pi acos(-1.0) #define eps 1e-10 int cmp(double x) { if(fabs(x)<eps) return 0; if(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<a.y; return x<a.x; } friend point operator *(const point &a,const double &b) { return point(a.x*b,a.y*b); } friend point operator *(const double &a,const point &b) { return point(a*b.x,a*b.y); } friend point operator /(const point &a,const double &b) { return point(a.x/b,a.y/b); } double norm() { return sqrt(sqr(x)+sqr(y)); } }; double det(const point &a,const point &b) { return a.x*b.y-a.y*b.x; } double dot(const point&a,const point &b) { return a.x*b.x+a.y*b.y; } double dist(const point &a,const point &b) { return (a-b).norm(); } point rotate_point(const point &p,double A) { double tx=p.x,ty=p.y; return point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A)); } point rotate(const point &p,double cost,double sint) { double x=p.x,y=p.y; return point(x*cost-y*sint,x*sint+y*cost); } pair<point,point> 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<point,int> 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<int> 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<top;i++) { if(!inra(my[i-1],my[i])) return false; } return true; } int main() { int ca=1; int cas; scanf("%d",&cas); while(cas--) { mp.clear(); scanf("%d",&n); ID=0; for(int i=1;i<=n;i++) { ra[i].c.input(); scanf("%lf",&ra[i].r); } printf("Case %d: ",ca++); if(cal(ra[1].c,ra[n].c)) //冲榜都靠这个特判#_# { printf("%.4f\n",dist(ra[1].c,ra[n].c)); continue; } en=0; memset(head,-1,sizeof(head)); int top=0; for(int i=1;i<=n;i++) { mp[ra[i].c]=++ID; que[top++]=ID; xx[ID]=ra[i].c; for(int j=i+1;j<=n;j++) { if(dist(ra[i].c,ra[j].c)>(ra[i].r+ra[j].r)+0.0) continue; pair<point,point> 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<top;i++) { for(int j=i+1;j<top;j++) { if(cal(xx[que[i]],xx[que[j]])) { add(que[i],que[j],dist(xx[que[i]],xx[que[j]])); } } } spfa(1); if(d[ID]>=1000000000) puts("No such path."); else printf("%.4f\n",d[ID]); } return 0; } /* 99 2 0 0 1 2 0 1 2 0 0 1 4 1 2 4 -4 0 1 -1 0 2 1 0 2 4 0 1 3 -3 0 1 0 0 2 0 3 1 3 -3 0 1 0 0 2 -2 -1 1 3 -3 0 1 -2 -1 1 0 0 2 4 2 2 2 2 -2 2 -2 2 2 -2 -2 2 2 0 0 3 1 0 1 3 0 0 1 2 2 2 3 0 1 3 0 0 1 3 0 1 2 2 2 ans: 2.0000 No 8.0000 4.8284 1.4142 3.0000 6.8284 1.0000 3.0654 2.8284 */
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116566.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...