QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#331576#5588. Eroding Pillarsngungu46WA 0ms4140kbC++142.5kb2024-02-18 15:25:302024-02-18 15:25:30

Judging History

你现在查看的是最新测评结果

  • [2024-02-18 15:25:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4140kb
  • [2024-02-18 15:25:30]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
#include <complex>
#include <ctime>
#include <cassert>
#include <functional>

#define REP(i,s,t) for(i=(s);i<(t);i++);
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<long long, long long> pi;
typedef vector<ll> vl;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<vector<ll> > mat;
typedef priority_queue<ll, vector<ll>, greater<ll> > minpq;
const ll inf = 1ll << 60;
const ll mod = 1e9 + 7;
const long long maxn = 1001;
const double eps = 1e-9;


int n;
vector<pair<ll, ll> > c(maxn);
vector<bool> visited;
vector<int> tin, low;
vector<bool> cut;
int timer;

double dist(pi a, pi b){
    double dx = a.first - b.first, dy = a.second - b.second;
    return sqrt(dx*dx+dy*dy);
}

void dfs(vector<vector<int> > &adj, int v, int p = -1){
    visited[v] = true;
    tin[v] = low[v] = timer++;
    int children = 0;
    for(int to: adj[v]){
        if(to == p) continue;
        if(visited[to]){
            low[v] = min(low[v], tin[to]);
        }

        else{
            dfs(adj, to, v);
            low[v] = min(low[v], low[to]);
            if(low[to] >= tin[v] && p !=-1) cut[v] = true;
            ++children;
        }
    }
    if(p==-1 && children > 1) cut[v] = true;
}

int is_possible(double d){
    vector<vector<int> > adj(n+1);
    for(int i = 0; i < n+1; i++){
        for(int j = i+1; j < n+1; j++){
            if(dist(c[i], c[j]) <= d){
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    timer = 0;
    visited.assign(n+1, false);
    tin.assign(n+1, -1);
    low.assign(n+1, -1);
    cut.assign(n+1, false);
    dfs(adj, 0);
    for(int i = 1; i < n+1; i++){
        if(!visited[i]) return false;
    }
    for(int i = 1; i < n+1; i++){
        if(cut[i]) return false;
    }
    return true;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> c[i].first >> c[i].second;
    }
    c[0] = make_pair(0, 0);

    double lo = 0, hi = 1e9+1;
    while(hi-lo > 1e-6){
        double mid = (lo+hi)/2;
        if(is_possible(mid)) hi=mid;
        else lo=mid;
    }

    printf("%0.9f\n", lo);
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 4132kb

input:

2
1 1
1 0

output:

1.414212748

result:

ok found '1.4142127', expected '1.4142136', error '0.0000006'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4044kb

input:

8
1 1
0 1
1 0
2 0
0 2
2 1
1 2
2 2

output:

0.999999196

result:

ok found '0.9999992', expected '1.0000000', error '0.0000008'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 4140kb

input:

1
1000000000 -1000000000

output:

1000000000.999999046

result:

wrong answer 1st numbers differ - expected: '1414213562.3730950', found: '1000000000.9999990', error = '0.2928932'