radar.java

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

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;


class Graph {
        static final int maxn = 100;
        static final int maxm = 201;
        static final int mmax = maxn * maxm + maxn + maxm + 100;
        int n, m;
        int[][] adj;
        void clear() {
            n = m = 0;
            adj = new int[maxn][maxm];
        }
        void insert(int u, int v) {
        	n = Math.max(n, u + 1);
        	m = Math.max(m, v + 1);
            adj[u][v] = 1;
        }
        boolean ok(int k) {
            build_dlx();
            return dfs(0, k);
        }
        int head;
        int[] U = new int[mmax], D = new int[mmax], L = new int[mmax], R = new int[mmax], 
            CN = new int[mmax], RN = new int[mmax];
        void addUD(int a, int h) {
            U[a] = h;
            D[a] = D[h];
            U[D[h]] = a;
            D[h] = a;
            CN[a] = h;
        }
        void addLR(int a, int h) {
            L[a] = h;
            R[a] = R[h];
            L[R[h]] = a;
            R[h] = a;
            RN[a] = h;
        }
        void add(int k, int r, int c) {
            addUD(k, c);
            addLR(k, r);
        }
        void remove(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(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] != 0) {
                        addLR(cnt, m + i);
                        addUD(cnt, j);
                        cnt++;
                    }
                }
            }
        }
        int h() {
            int[] hash = new int[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;
        }
        boolean 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;
        }
}
public class Radar {
	static Graph g = new Graph();
	static Scanner cin = new Scanner(System.in);
	static class P {
	    int x, y;
	    P (int _x, int _y) {
	    	x = _x;
	    	y = _y;
	    }
	    P () {}
	    P input() {
	    	x = cin.nextInt();
	    	y = cin.nextInt();
	    	return this;
	    }
	};

	static P[] dt = new P[210], base = new P[210];
	static int n, m, k;
	static int dist2(P a, P b) {
	    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
	}

	static boolean ok(int lim) {
	    g.clear();
	    boolean[] flag = new boolean[n];
	    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);
	}
	static List<Integer> unique(List<Integer> hash) {
		List<Integer> ans = new ArrayList<Integer>();
		for (int i = 0; i < hash.size(); ++i) {
			if (i == 0 || hash.get(i) != hash.get(i - 1)) {
				ans.add(hash.get(i));
			}
		}
		return ans;
	}
	static double solve() {
	    List<Integer> hash = new ArrayList<Integer>();
	    for (int i = 0; i < n; ++i) {
	        for (int j = 0; j < m; ++j) {
	            hash.add(dist2(dt[i], base[j]));
	        }
	    }
	    Collections.sort(hash);
	    hash = unique(hash);
	    int ans = Integer.MAX_VALUE;
	    int s = 0, t = hash.size() - 1;
	    while (s <= t) {
	        int mid = (s + t) / 2;
	        if (ok(hash.get(mid))) {
	        	ans = hash.get(mid);
	            t = mid - 1;
	        } else {
	            s = mid + 1;
	        }
	    }
	    return Math.sqrt(ans + 0.0);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
	    int ca;
	    ca = cin.nextInt();
	    while (ca-- > 0) {
	    	n = cin.nextInt();
	    	m = cin.nextInt();
	    	k = cin.nextInt();
	        for (int i = 0; i < n; ++i) {
	            dt[i] = new P().input();
	        }
	        for (int i = 0; i < m; ++i) {
	            base[i] = new P().input();
	        }
	        System.out.printf("%.6f\n", solve());
	    }
	}
}