QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#50444 | #2040. Physical Distancing | Isaacxie | WA | 2ms | 3896kb | C++20 | 1.7kb | 2022-09-26 05:16:57 | 2022-09-26 05:16:58 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cmath>
using namespace std;
const int N = 110, M = N * N * 2;
const double eps = 1e-7;
#define x first
#define y second
typedef pair<int,int> PII;
int l, w, n;
PII p[N];
int h[N], ne[M], e[M], idx;
bool st[N];
void add(int a, int b) {
ne[idx] = h[a], e[idx] = b, h[a] = idx ++;
}
double get_dist(PII a, PII b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
bool dfs(int u) {
if (u == n + 1) return false;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
st[j] = true;
if (!dfs(j)) return false;
}
}
return true;
}
bool check(double mid) {
memset(h, -1, sizeof(h));
memset(st, false, sizeof(st));
idx = 0;
for (int i = 1; i <= n; i ++) {
for (int j = i + 1; j <= n; j ++) {
if (get_dist(p[i], p[j]) <= mid) add(i, j), add(j, i);
}
}
for (int i = 1; i <= n; i ++) {
if (p[i].y <= mid) add(0, i), add(i, 0);
if (p[i].y >= w - mid) add(n + 1, i), add(i, n + 1);
}
st[0] = true;
return dfs(0);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> l >> w >> n;
for (int i = 1; i <= n; i ++) {
cin >> p[i].x >> p[i].y;
}
double l = 0 , r = 100;
while (r - l > eps) {
double mid = (l + r) / 2.0;
if (check(mid)) l = mid;
else r = mid;
}
cout << fixed << setprecision(6);
cout << r << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3896kb
input:
100 100 1 50 50
output:
50.000000
result:
ok found '50.00000', expected '50.00000', error '0.00000'
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3780kb
input:
100 2 2 49 0 51 2
output:
2.000000
result:
wrong answer 1st numbers differ - expected: '1.41421', found: '2.00000', error = '0.41421'