Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define foreach(it,v) for (__typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
typedef long long ll;
const int N = 1005;
bool check(int n, double x[], double y[], double r[]) {
const double eps = 1e-6;
const double INF = 1e6;
double L = -INF, R = INF, U, D;
rep (i, n) {
L = max(L, x[i] - r[i]);
R = min(R, x[i] + r[i]);
}
if (L + eps < R) {
rep (o, 40) {
double mid = (L + R) / 2;
D = -INF; U = INF;
int j, k;
rep (i, n) {
double d = sqrt(r[i] * r[i] - (x[i] - mid) * (x[i] - mid));
if (y[i] + d < U) {
U = y[i] + d;
j = i;
}
if (y[i] - d > D) {
D = y[i] - d;
k = i;
}
}
if (D + eps < U) return 1;
if ((x[j] - x[k]) * (x[j] - x[k]) + (y[j] - y[k]) * (y[j] - y[k]) + eps > (r[j] + r[k]) * (r[j] + r[k])) return 0;
if (x[j] > x[k]) swap(j, k);
double curx = x[j] + r[j] / (r[j] + r[k]) * (x[k] - x[j]);
if (curx < mid) {
R = mid;
} else {
L = mid;
}
}
return 0;
} else {
return 0;
}
}
int main() {
#ifdef debug
freopen("in", "r", stdin);
#endif
int n;
static double x[N], y[N], r[N];
while (scanf("%lf%lf%lf", x, y, r + 1) != EOF) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lf%lf", x + i, y + i);
r[i] = r[1];
}
r[0] = 1e6;
if (!check(n + 1, x, y, r)) {
puts("X");
} else {
double L = 0, R = 1e6, mid;
rep (i, 40) {
mid = (L + R) / 2;
r[0] = mid;
if (check(n + 1, x, y, r)) {
R = mid;
} else {
L = mid;
}
}
printf("%.2f\n", L);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment