同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21697_Christmas

2022-5-16 18:20| 发布者: Hocassian| 查看: 21| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505768620499-Problem List-采集的数据-后羿采集器.html

Pro.ID

21697

Title

Christmas

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21697

AC

Submit

Ratio

时间&空间限制

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

描述

Christmas day is coming. There will be a ball in Christmas Eve. N men and N women will take part in the ball. One man and one woman form a pair. As we know, if there is a great difference in age or in height, the pair will be very disappointed. Now we define the disappointment between one man and one woman as:

F(i, j)=(H_i - H_j)² + (AGE_i - AGE_j)²

Where H_i is the height of person i and AGE_i is the age of that person. Your task is to find a plan to form N pairs, with the max disappointment value minimized.

输入

Input may contain several test data sets.

For each data set, the first line contains an integer N ( 0 < N ≤ 500 );

The first line is followed by 2N lines. The first N lines describe N men, and the last N lines describe N women. Each line contains two integers, the height and the age of a person.

You can assume that the height of one person is between 100cm and 200cm and the age is between 10 and 60.

Input is ended by N=0, which should not be processed.

输出

Description

F(i, j)=(H_i - H_j)² + (AGE_i - AGE_j)²

Where H_i is the height of person i and AGE_i is the age of that person. Your task is to find a plan to form N pairs, with the max disappointment value minimized.

Input

Input may contain several test data sets.

For each data set, the first line contains an integer N ( 0 < N ≤ 500 );

The first line is followed by 2N lines. The first N lines describe N men, and the last N lines describe N women. Each line contains two integers, the height and the age of a person.

You can assume that the height of one person is between 100cm and 200cm and the age is between 10 and 60.

Input is ended by N=0, which should not be processed.

Output

For each data set, print the answer in a single line.

Sample Input

2
141 27
134 10
169 34
178 18
0

Sample Output

1801

Source

ZS 2007 pre