圣诞节

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 christmas.in 输出文件 christmas.out

【问题描述

圣诞节要来了,有一个舞会.N个男士和N个女士将要参加.一个男士和一个女士成为一对舞伴.我们知道,如果一对舞伴的年龄和身高相差太多的话会不够和协.现在我们定义一个男士和一个女士的不和协值如下:

F(i,j)=(Hi-Hj)^2+(AGEi-AGEj)^2
Hi是i号人员的身高,AGEi是i号人员的年龄.你的任务是设计一个舞伴搭配方案,使最大不合协值最小.
【输入格式】
输入数据第一行为一个正整数N(N≤500),接下来有2N行;每行包含两个正整数x,y,表示身高和年龄(100 ≤x≤200,10≤y≤60),前N个表示男士,后N个表示女士。
【输出格式】

输出只有一个整数,表示最小的最大不和协值。

【输入样例】
输入文件名: christmas.in
2
141 27
134 10
169 34
178 18
输出文件名: christmas.out
1801