| ||||||||||
| 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