# 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

## Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1000;
const double eps = 1e-8;
{
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)
{
}

int n, b, r;
double x[2 * N], y[2 * N];
{
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()
{