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

二分搜索加DFS AC的,还有一定要注意不是.lf,而是.f 也不知知道是为什么,哈哈

Posted by 4564 at 2018-08-22 20:10:23 on Problem 2253
#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:
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