QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#331576 | #5588. Eroding Pillars | ngungu46 | WA | 0ms | 4140kb | C++14 | 2.5kb | 2024-02-18 15:25:30 | 2024-02-18 15:25:30 |
Judging History
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'