网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
圣诞节
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | christmas.in | 输出文件 | christmas.out |
【问题描述】
圣诞节要来了,有一个舞会.N个男士和N个女士将要参加.一个男士和一个女士成为一对舞伴.我们知道,如果一对舞伴的年龄和身高相差太多的话会不够和协.现在我们定义一个男士和一个女士的不和协值如下:
F(i,j)=(Hi-Hj)^2+(AGEi-AGEj)^2
Hi是i号人员的身高,AGEi是i号人员的年龄.你的任务是设计一个舞伴搭配方案,使最大不合协值最小.
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
141 27
134 10
169 34
178 18
输出文件名: christmas.out
1801