Preparing NOJ

Christmas

2000ms 65536K

Description:

     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 :

    

    difference[i][j]=(Hman[i] - Hwoman[j]) * (Hman[i] - Hwoman[j]) + (Aman[i] - Awoman[j]) * (Aman[i] - Awoman[j])


     Where Hi 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 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

Note:

本题由旧版NOJ导入,来源:NUPT ACM

Info

NOJ

Provider NOJ

Code NOJ1134

Tags

Submitted 3

Passed 2

AC Rate 66.67%

Date 04/20/2019 10:03:10

Related

Nothing Yet