# Easter Eggs

Easter is coming and the Easter Bunny decided to organise a chocolate egg hunt for the children. He will hide two types of eggs: blue milk chocolate and red dark chocolate. In the field there are some redberry and some blueberry plants where the Easter Bunny could hide the eggs. Red eggs should be hidden in a redberry plant and blue eggs in a blueberry plant. The local government has issued a permit for the event, under the condition that exactly N eggs are hidden. As they do not pay for the dental care plans of the local children, the Easter Bunny gets to decide himself how many eggs to hide of each colour. According to the yearly tradition, there is a big reward for the first child to find both a red and a blue egg. In order to make the hunt as challenging as possible, the Easter Bunny wants to maximise the minimum distance between a red and a blue egg. To keep things fair, he will hide at most one egg in each plant. Your task is to write a program to help him accomplish his goal.

# Input

One line containing three integers N,B,R, the number of eggs to hide N ≤ 250, the number of blueberry plants B < N and the number of redberry plants R < N;

• B lines, each containing two integers −104 ≤ x,y ≤ 104, indicating the coordinates (x, y) of a blueberry plant;
• R lines, each containing two integers −104 ≤ x,y ≤ 104, indicating the coordinates (x, y) of a redberry plant.

The B + R plants are guaranteed to have distinct coordinates. Moreover, N is guaranteed to satisfy N ≤ B + R. Output

# Output

Output a single line containing a floating point number, D, the largest minimum distance between a red and a blue egg that can be achieved. You are required to output D with absolute precision 10−6, i.e. with at least 6 decimal places.

# Example

Input 1

3 2 2
0 0
1 0
2 0
3 0

Output 1

2.000000000000000

Input 2

4 3 3
0 0
1 2
-1 2
0 1
-1 -1
1 -1

Output 2

3.000000000000000

# Solution

# 题意

给出两类点，选出其中恰好n个点使得选中的点中不同类的点距离最远。

# 思路

可以发现答案满足二分性质。问题转化成在只选用距离不小于某个值d的边的时候能否选出n个点。 对于这个问题，可以将距离小于某个值d的边保留，构建二分图。二分图中的点，如果A连了B和C，那么选了A就不能选B和C，选了B或C就不能选A，否则该方案会拉低最小距离d。换句话说这个二分图的点，每条边的两个端点只能保留一个。那么就是一个最小覆盖数问题，其等同于求最大匹配数。 对于只有距离大于等于d的边的点来说，它可以任意选取。

# Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1000;
const double eps = 1e-8;
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || '9' < ch)
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while ('0' <= ch && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

struct edge_
{
    int to, next; double w;
} edge[2 * N * N];
int head[2 * N], cnt = 0;
int u[N * N], v[N * N]; double d[N * N]; int tag[N * N], cntt = 0;
void insert(int u, int v, double w)
{
    edge[++cnt] = (edge_){v, head[u], w};
    head[u] = cnt;
}


int n, b, r;
double x[2 * N], y[2 * N];
void readin()
{
    scanf("%d%d%d", &n, &b, &r);
    for (int i = 1; i <= b; ++i)
        scanf("%lf%lf", x + i, y + i);
    for (int i = 1; i <= r; ++i)
        scanf("%lf%lf", x + b + i, y + b + i);
}

double sqr(double x)
{
    return x * x;
}
bool cmp(const int &a, const int &b)
{
    return d[a] > d[b];
}

int nn;
void init()
{
    nn = b + r;
    for (int i = 1; i <= b; ++i)
        for (int j = b + 1; j <= nn; ++j)
        {
            ++cntt;
            u[cntt] = i;
            v[cntt] = j;
            d[cntt] = sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j]));
            tag[cntt] = cntt;
        }   
    sort(tag + 1, tag + cntt + 1, cmp);
    for (int i = 1; i <= cntt; ++i)
        insert(u[tag[i]], v[tag[i]], d[tag[i]]);
}

bool used[2 * N]; int match[2 * N];
bool find(int x, double limit)
{
    for (int i = head[x]; i; i = edge[i].next)
    {
        if (edge[i].w >= limit)
            break;
        int v = edge[i].to;
        if (used[v] == false)
        {
            used[v] = true;
            if (match[v] == 0 || find(match[v], limit))
            {
                match[v] = x;
                return true;
            }
        }
    }
    return false;
}
void solve()
{
    double l = 0, r = 1e9, ans;
    while (fabs(r - l) > eps)
    {
        double mid = (l + r) / 2.0;
        int all = 0;
        memset(match, 0, sizeof(match));
        for (int i = 1; i <= nn; i++)
        {
            memset(used, 0, sizeof(used));
            if (find(i, mid))
                ++all;
        }
        if (nn - all >= n)
            l = mid;
        else
            r = mid;
    }
    printf("%.6lf\n", l);
}
int main()
{
    readin();
    init();
    solve();
    return 0;
}