Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

123

Posted by 1745073284 at 2018-10-01 15:05:38 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);
} 
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator