Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
123#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<queue> using namespace std; const int maxn = 10050; struct node { double x,y,r; } T[maxn]; int n,m,q; vector<int> f[maxn]; vector<double> g[maxn]; queue<int> qu; double A,B,C1,C2,dis[maxn],eps=1e-8; bool vis[maxn]; double sqr(double x) { return x*x; } double dist(int x,int y) { return sqrt(sqr(T[x].x-T[y].x)+sqr(T[x].y-T[y].y)); } double dist2(int i,int num) { double C0; if(num==1) C0=C1; if(num==2) C0=C2; return abs(A*T[i].x+B*T[i].y+C0)/sqrt(A*A+B*B); } void add_edge(int x,int y,double dis) { f[x].push_back(y);f[y].push_back(x); g[x].push_back(dis);g[y].push_back(dis); } void spfa() { for(int i=1;i<=n+1;i++) dis[i]=1e10; qu.push(0); vis[0]=true; while(!qu.empty()) { int u=qu.front(); qu.pop(); for(int i=0;i<f[u].size();i++) { int v=f[u][i]; if(dis[v]>dis[u]+g[u][i]) { dis[v]=dis[u]+g[u][i]; if(!vis[v]) { qu.push(v); vis[v]=true; } } } vis[u]=false; } } int main() { scanf("%d",&n); scanf("%lf%lf%lf%lf",&A,&B,&C1,&C2); for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&T[i].x,&T[i].y,&T[i].r); add_edge(0,n+1,abs(C1-C2)/sqrt(A*A+B*B)); for(int i=1;i<=n;i++) { double res=dist2(i,1)-T[i].r; if(res<-eps) add_edge(0,i,0); else add_edge(0,i,res); res=dist2(i,2)-T[i].r; if(res<-eps) add_edge(i,n+1,0); else add_edge(i,n+1,res); } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ double res=dist(i,j)-(T[i].r+T[j].r); if(res<-eps) add_edge(i,j,0); else add_edge(i,j,res); } } spfa(); printf("%.8lf",dis[n+1]); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator