Problem

With the help of the Ares L, the Emperor of Law and some stars of the future, General M succeeded in setting foot on the mountain, and had set up a kingdom, known as ACMSYSU. In order to reward these founding heroes, General M decided to share her network.
General M has manufactured a router. One can use this network if the Euclidean distance between his/her house and the router is not greater than d. Because of General M's excellent technology, the distance between her house and the router can be infinite.
There are n heroes in the kingdom besides General M. General M is not an eccentric person, so she hopes everyone can use the network. Because the farther the router is away from her house, the worse the signal, General M wants the router being as close to her house as possible. Please help General M place the router so that the distance between her house and the router is minimized, and every one can use the router. You just need to tell General M the minimum distance.

Input

The input will consist of multiple test cases.
For each case, the first line contains 3 integers x, y and d, which represent that the General M's house locates at the point (x, y) and one can use the network if his/her distance to the router is not greater than d.
The second line is a positive integer n, the number of heroes of the kingdom.
Then n lines follow. Each line has 2 integers x_i and y_i, indicating that the i-th hero locates at point (x_i, y_i)。
All integers in the input satisfy that their absolute values are less than or equal to 10^5, and 1<=n<=10^3.

Output

For each case, output a real number which indicates the minimum distance between the General M's house and the router, to two decimal places.
If it is impossible to share a network which can cover everyone, output an 'X' (without the single quote).

Sample Input

0 0 5
2
5 3
5 -3
0 0 1
2
5 3
5 -3

Sample Output

1.00
X

思路

分这样几种情况讨论：
①如果路由器恰好放在主人家的位置上即可覆盖到所有英雄，那么答案就是0.00；
②如果以路由器为圆心的圆周上只有一个点，则圆心在连线上；
③如果以路由器为圆心的圆周上有两个或多个点，则当两个点或者更多的点都距离为d时确定圆心；
复杂度：O（n³），是的没错，这个复杂度也可以过……这点又给学长指出来了，所以以后有复杂度更优的做法再补。

代码一

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const double PI = acos(-1.0);
const double EPS = 1e-8;
const double INF = 0x3f3f3f3f;
const int M = 1005;
int n;
double x, y, d;
struct Point {
    double x, y;
    Point() {}
    Point(double _x, double _y) :x(_x), y(_y) {}
    Point operator+(Point p) { return Point(x + p.x, y + p.y); }
    Point operator-(Point p) { return Point(x - p.x, y - p.y); }
    Point operator*(double p) { return Point(p*x, p*y); }
    Point operator/(double p) { return Point(x / p, y / p); }
    Point operator+=(Point p) { *this = *this + p; return *this; }
    Point operator-=(Point p) { *this = *this - p; return *this; }
    Point operator*=(double p) { *this = *this * p; return *this; }
    Point operator/=(double p) { *this = *this / p; return *this; }
    bool operator==(Point p) { return abs(x - p.x)<EPS&&abs(y - p.y)<EPS; }
    bool operator!=(Point p) { return !(*this == p); }
    double dot(Point p) { return x*p.x + y*p.y; }
    double det(Point p) { return x*p.y - y*p.x; }
    double length() { return sqrt(x*x + y*y); }
    Point rotate(double rad) { return Point(x*cos(rad) - y*sin(rad), x*sin(rad) + y*cos(rad)); }
}arr[M];
bool judge(Point p) {
    for (int i = 1; i <= n; i++) {
        Point t = arr[i] - p;
        if (t.length()>d&&abs(t.length() - d)>EPS)return false;
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(2);
    while (cin >> x >> y >> d) {
        memset(arr, 0, sizeof(arr));
        arr[0] = Point(x, y);
        cin >> n;
        for (int i = 1; i <= n; i++)cin >> arr[i].x >> arr[i].y;
        if (judge(arr[0])) { cout << "0.00" << endl; continue; }
        double min_value = INF;
        for (int i = 1; i <= n; i++) {
            Point t = arr[0] - arr[i];
            t *= (d / t.length()); 
            t += arr[i];
            Point t0 = t - arr[0];
            if (t0.length()<min_value&&judge(t))min_value = t0.length();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                Point t = (arr[i] + arr[j]) / 2.0;
                Point t0 = arr[i] - arr[j];
                double dis = 0.5*t0.length();
                Point vec1 = t0.rotate(PI / 2.0)*sqrt(d*d - dis*dis) / (dis*2.0);
                Point vec2 = t0.rotate(-PI / 2.0)*sqrt(d*d - dis*dis) / (dis*2.0);
                Point t1 = t + vec1, t2 = t + vec2;
                Point t3 = t1 - arr[0], t4 = t2 - arr[0];
                if (t3.length()<min_value&&judge(t1))min_value = t3.length();
                if (t4.length()<min_value&&judge(t2))min_value = t4.length();
            }
        }
        if (abs(min_value - INF)<EPS)cout << "X" << endl;
        else cout << min_value << endl;
    }
    return 0;
}

代码二

学长的二分AC代码先贴这里，速度确实快了不少，然而在我自己电脑上跑不出正确结果但是hdu可以AC？先马了以后看~~

#include<cstdio>
#include<utility>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 1005;
const double pi = acos(-1.0);
const double eps = 1e-6;
pair<double, double> fr[maxn], center;
double d;
int n;
pair<double, double> operator+(const pair<double, double> a, const pair<double, double> b) {
    return pair<double, double>(a.first + b.first, a.second + b.second);
}
pair<double, double> operator-(const pair<double, double> a, const pair<double, double> b) {
    return pair<double, double>(a.first - b.first, a.second - b.second);
}
pair<double, double> operator*(const pair<double, double> a, const double s) {
    return pair<double, double>(a.first*s, a.second*s);
}
pair<double, double> operator/(const pair<double, double> a, const double s) {
    return pair<double, double>(a.first / s, a.second / s);
}
double norm(pair<double, double> x) {
    return sqrt(x.first*x.first + x.second*x.second);
}
pair<double, double> rotate(const pair<double, double> &p, double cost, double sint) {
    return pair<double, double>(p.first*cost - p.second*sint, p.first*sint + p.second*cost);
}
pair<pair<double, double>, pair<double, double>> crosspoint(pair<double, double> ap, double ar, pair<double, double> bp, double br) {
    double d = norm(ap - bp);
    double cost = (ar*ar + d*d - br*br) / (2 * ar*d);
    double sint = sqrt(1.0 - cost*cost);
    pair<double, double> v = (bp - ap) / norm(bp - ap)*ar;
    return make_pair(ap + rotate(v, cost, -sint), ap + rotate(v, cost, sint));
}
int sgn(double x) {
    if (x<-eps)return -1;
    return x>eps;
}
bool ifinclude(pair<double, double> a, double ar, pair<double, double> b, double br) {
    return sgn(norm(a - b) - (ar + br))<0 && sgn(norm(a - b) - abs(ar - br))>0;
}
bool check(double r) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (ifinclude(pair<double, double>(0, 0), r, fr[i], d)) {
            cnt++;
            auto cpt = crosspoint(pair<double, double>(0, 0), r, fr[i], d);
            bool flg = true;
            for (int i = 1; i <= n; i++)
                if (sgn(norm(cpt.first - fr[i]) - d)>0) { flg = false; break; }
            if (flg)return true;
            flg = true;
            for (int i = 1; i <= n; i++)
                if (sgn(norm(cpt.second - fr[i]) - d)>0) { flg = false; break; }
            if (flg)return true;
        }
    }
    return cnt == 0;
}
bool sol() {
    int cx, cy, cd;
    if (!(~scanf("%d%d%d", &cx, &cy, &cd)))return false;
    d = cd;
    double l = 0, r = 1e10;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int tx, ty;
        scanf("%d%d", &tx, &ty);
        fr[i] = pair<double, double>(tx - cx, ty - cy);
        l = max(l, norm(fr[i]) - d);
        r = min(r, norm(fr[i]) + d);
    }
    if (sgn(l - r) >= 0) { puts("X"); return true; }
    bool flg = false;
    while (r - l>eps) {
        double mid = (l + r) / 2;
        if (check(mid))r = mid, flg = true;
        else l = mid;
    }
    if (flg)printf("%.2lf\n", (double)l);
    else printf("X\n");
    return true;
}
int main() {
    while (sol());
    return 0;
}