比赛 20120418x 评测结果 AAAAAA
题目名称 圣诞节 最终得分 100
用户昵称 王者自由 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-04-18 14:56:45
显示代码纯文本
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 500 + 10;
int n, m, h[2][N], a[2][N], F[N][N];
int x[N], y[N], l[N*N], u, s; 
bool g[N];
inline int sqr(int x) {
    return x * x;
}
bool DFS(int a) {
    for(int i=1; i<=n; i++)
        if(F[a][i] <= u && !g[i]) {
            g[i] = 1;
            if(!y[i] || DFS(y[i])) {
                y[i] = a, x[a] = i;
                return true;
            }
        }
    return false;
}
int main() {
    freopen("christmas.in", "r", stdin);
    freopen("christmas.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d %d", h[0]+i, a[0]+i);
    for(int i=1; i<=n; i++)
        scanf("%d %d", h[1]+i, a[1]+i);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            F[i][j] = l[++m] = sqr(h[0][i] - h[1][j]) + sqr(a[0][i] - a[1][j]);
    sort(l+1, l+m+1);
    for(int i=n; i!=m; i++) {
        while(l[i] == l[i-1]) i++;
        u = l[i];
        for(int j=1; j<=n; j++) if(!x[j]) {
            for(int k=1; k<=n; k++) g[k] = 0;
            if(DFS(j)) s++;
            if(s == n) {
                printf("%d\n", u);
                return 0;
            }
        }
    }
    return 0;
}