| ||||||||||
| 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 | |||||||||
二分搜索加DFS AC的,还有一定要注意不是.lf,而是.f 也不知知道是为什么,哈哈#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
#define INF 0x3f3f3f3f
int n,vis[220];
double mp[220][220],dis[220];
struct AX{
int x;
int y;
}point[220];
vector<double> mx[220];
double Get_dis(AX a,AX b){
int x=a.x-b.x,y=a.y-b.y;
return sqrt(x*x*1.0+y*y*1.0);
}
bool DFS(int k,double v){
vis[k]=1;
for(int i=1;i<=n;i++){
if(vis[i])continue;
if(mp[k][i]>v)continue;
else if(i!=2){
if(DFS(i,v)) return true;}
else
return true;
}
return false;
}
int main(){
int casen=1;
while(scanf("%d",&n)==1&&n){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j)mp[i][j]=0.0;
else mp[i][j]=INF*1.0;
for(int i=1;i<=n;i++)scanf("%d%d",&point[i].x,&point[i].y);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
mp[i][j]=Get_dis(point[i],point[j]);
double R=mp[1][2],L=0.0,mid;
while(R-L>0.00001){
mid=(L+R)*1.0/2;
memset(vis,0,sizeof(vis));
if(DFS(1,mid))R=mid;
else
L=mid;
}
printf("Scenario #%d\n",casen++);
printf("Frog Distance = %.3f\n",mid);
printf("\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator