BNU Flash Mob - from lanshui_Yang

Flash Mob

Jumping Jack is in charge of organizing a ?ash mob. Themembers of the ?ash mob move around town all day and part of the appeal of thisgroup is they come together to do their thing whenever the mood strikes Jack.When the mood does strike,Jack sends a text message to the members to meet ata particular intersection in town in exactly one hour. The streets of the townrun only north-south or eastwest and are evenly spaced,forming a perfect gridlike a sheet of graph paper. Due to the spontaneity,Jack wants to minimizethe inconvenience and so picks an intersection to minimize the total distance traveledby the ?ash mob’s members. Fortunately Jack has the locations of all themembers via the GPS on their cell phones. Your job is to ?nd the meetinglocation given all the members’ locations. Each intersection will be given by apair of non-negative integers; the ?rst coordinate is the east-west street andthe second coordinate is the north-south street. The location of each ?ash mobmember will be an intersection. Members can travel only north-south or east-westbetween intersections.

?For example,suppose there are 5 mob members at locations (3,4),(0,5),(1,1),(5,and(5,5). Then if Jack summons them all to location (3,the total number ofblocks traveled by the mob members would be 14. Jack could do no better – butsometimes the ‘best’ location may not be unique.

Input

Input for each test case will bea series of integers on one or more lines. The ?rst integer,n (1 ≤ n ≤ 1000),indicates the number of mob members. There follow n pairs of integersindicating the location (intersection) of each member. The location coordinatesare both between 0 and 10^6,inclusive. More than one member may be at the sameintersection. A line containing 0 will follow the last test case.

Output

Output one line for each testcase in the format given below. The ordered pair is the coordinates of thelocation in the city where the total distance traveled (in blocks) is minimal.If there is more than one such location,output the one with the smallest ?rstcoordinate. If there is more than one ‘best’ location with the smallest ?rstcoordinate,output the one of those with the smallest second coordinate. Thetotal number of blocks traveled by all the mob members follows the location.

Sample Input

5 3 4 0 5 1 1 5 5 5 5

4 100 2 100 2 100 2 1 20000

0

Sample Output

Case 1: (3,5) 14

Case 2: (100,2) 20097

? ? ? 题目大意：给你n个点，其坐标形式为（x，y），让你在这个二维坐标系中找一个点M，其坐标为（a，b），使这n个点与点M的曼哈顿距离之和最短。曼哈顿距离:在平面上，坐标为（x1,y1）的 i 点 与 坐标为（x2,y2）的 j 点的曼哈顿距离为：

#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std ;
const int MAXN = 2005 ;
int n ;
int X[MAXN] ;
int Y[MAXN] ;
int ca ;
void init()
{
    int i ;
    for(i = 0 ; i < n ; i ++)
    {
        scanf("%d",&X[i]) ;
        scanf("%d",&Y[i]) ;
    }
}
void solve()
{
    sort(X,X + n) ;
    sort(Y,Y + n) ;
    int ans = 0 ;
    int i ;
    for(i = 0 ; i < n ; i ++)
    {
        ans += abs(X[i] - X[(n - 1)/ 2]) ;
        ans += abs(Y[i] - Y[(n - 1) / 2]) ;
    }
    printf("Case %d: (%d,%d) %dn",++ ca,X[(n - 1)/ 2],Y[(n - 1)/ 2],ans) ;
}
int main()
{
    ca = 0 ;
    while (scanf("%d",&n) != EOF)
    {
        if(n == 0)
        break ;
        init() ;
        solve() ;
    }
    return 0 ;
}