radar.cpp

第四届百度杯编程大赛final解题报告+标程

/*
 * Author: ChaeYeon
 * Created Time:  2009/3/24 21:56:53
 * File Name: radar.cpp
 * Description: 
 */
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define out(x) fprintf(stderr, "%s: %I64d\n", #x, (long long)(x))
#define SZ(v) ((int)(v).size())
const int maxint=-1u>>1;
template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}

class Graph {
    public:
        static const int maxn = 100;
        static const int maxm = 201;
        static const int mmax = maxn * maxm + maxn + maxm + 100;
        int n, m;
        int adj[maxn][maxm];
        void clear() {
            n = m = 0;
            memset(adj, 0, sizeof(adj));
        }
        void insert(int u, int v) {
            get_max(n, u + 1);
            get_max(m, v + 1);
            adj[u][v] = 1;
        }
        bool ok(int k) {
            build_dlx();
            return dfs(0, k);
            for (int i = 1; i <= k; ++i) {
                if (dfs(0, i)) {
                    return true;
                }
            }
            return false;
        }
    private:
        int head;
        int U[mmax], D[mmax], L[mmax], R[mmax], 
            CN[mmax], RN[mmax];
        void addUD(const int &a, const int &h) {
            U[a] = h;
            D[a] = D[h];
            U[D[h]] = a;
            D[h] = a;
            CN[a] = h;
        }
        void addLR(const int &a, const int &h) {
            L[a] = h;
            R[a] = R[h];
            L[R[h]] = a;
            R[h] = a;
            RN[a] = h;
        }
        void add(const int &k, const int &r, const int &c) {
            addUD(k, c);
            addLR(k, r);
        }
        void remove(const int &k) {
            for (int j = R[k]; j != k; j = R[j]) {
                for (int i = D[j]; i != j; i = D[i]) {
                    L[R[i]] = L[i];
                    R[L[i]] = R[i];
                }
                D[U[j]] = D[j];
                U[D[j]] = U[j];
            }
        }
        void unremove(const int &k) {
            for (int j = L[k]; j != k; j = L[j]) {
                D[U[j]] = j;
                U[D[j]] = j;
                for (int i = U[j]; i != j; i = U[i]) {
                    L[R[i]] = i;
                    R[L[i]] = i;
                }
            }
        }
        void build_dlx() {
            head = mmax - 1;
            U[head] = D[head] = L[head] = R[head] = head;
            int cnt = 0;
            for (int i = 0; i < m; ++i) {
                U[cnt] = D[cnt] = cnt;
                addLR(cnt++, head);
            }
            for (int i = 0; i < n; ++i) {
                L[cnt] = R[cnt] = cnt;
                addUD(cnt++, head);
            }
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (adj[i][j]) {
                        addLR(cnt, m + i);
                        addUD(cnt, j);
                        cnt++;
                    }
                }
            }
        }
        int h() {
            int hash[maxm] = {};
            int ans = 0;
            for (int c = R[head]; c != head; c = R[c]) {
                if (hash[c] == 0) {
                    hash[c] = 1;
                    ++ans;
                    for (int j = D[c]; j != c; j = D[j]) {
                        for (int i = R[j]; i != j; i = R[i]) {
                            if (CN[i] != head) {
                                hash[CN[i]] = 1;
                            }
                        }
                    }
                }
            }
            return ans;
        }
        bool dfs(int k, int lim) {
            if (k + h() > lim) {
                return false;
            }
            if (R[head] == head) {
                return true;
            }
            int c;
            c = R[head];
            L[R[c]] = L[c];
            R[L[c]] = R[c];
            for (int i = D[c]; i != c; i = D[i]) {
                L[R[i]] = L[i];
                R[L[i]] = R[i];
            }
            for (int i = D[c]; i != c; i = D[i]) {
                remove(RN[i]);
                if (dfs(k + 1, lim)) {
                    return true;
                }
                unremove(RN[i]);
            }
            for (int i = U[c]; i != c; i = U[i]) {
                L[R[i]] = i;
                R[L[i]] = i;
            }
            L[R[c]] = c;
            R[L[c]] = c;
            return false;
        }
};
Graph g;

struct P {
    int x, y;
    P (int _x, int _y)
        :x(_x), y(_y) {}
    P () {}
    void input() {
        scanf("%d %d", &x, &y);
    }
};
P dt[210];
P base[210];
int n, m, k;
int dist2(P a, P b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool ok(int lim) {
    bool f[210] = {};
    int cnt[210];
    for (int i = 0; i < k; ++i) {
        int v = 0;
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (f[j] == 0 && dist2(base[i], dt[j]) <= lim) {
                    ++cnt[i];
                }
            }
            if (v == -1 || cnt[i] > cnt[v]) {
                v = i;
            }
        }
        for (int j = 0; j < n; ++j) {
            if (f[j] == 0 && dist2(base[v], dt[j]) <= lim) {
                f[j] = 1;
            }
        }
    }
    bool ok = true;
    for (int i = 0; i < n; ++i) {
        if (f[i] == 0) {
            ok = false;
            break;
        }
    }
    if (ok) {
        return true;
    }
    g.clear();
    bool flag[210] = {};
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dist2(base[i], dt[j]) <= lim) {
                flag[j] = true;
                g.insert(i, j);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (flag[i] == false) {
            return false;
        }
    }
    return g.ok(k);
}

double solve() {
//    printf("%d %d %d\n", n, m, k);
    vector<int> hash;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            hash.push_back(dist2(dt[i], base[j]));
        }
    }
    sort(hash.begin(), hash.end());
    hash.erase(unique(hash.begin(), hash.end()), hash.end());
    int ans = maxint;
    int s = 0, t = SZ(hash) - 1;
    while (s <= t) {
        int mid = (s + t) / 2;
        if (ok(hash[mid])) {
            get_min(ans, hash[mid]);
            t = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return sqrt(ans + 0.0);
}

int main() {
    int ca;
    scanf("%d", &ca);
    while (ca--) {
        scanf("%d %d %d", &n, &m, &k);
        for (int i = 0; i < n; ++i) {
            dt[i].input();
        }
        for (int i = 0; i < m; ++i) {
            base[i].input();
        }
        printf("%.6lf\n", solve());
    }
    return 0;
}