Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 123

Posted by 1745073284 at 2018-10-01 15:05:40 on Problem 3204
#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);
}
{
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);
for(int i=1;i<=n;i++)
{
double res=dist2(i,1)-T[i].r;
res=dist2(i,2)-T[i].r;
}
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);
}
}
spfa();
printf("%.8lf",dis[n+1]);
return 0;
}

Followed by: