学步园

Flash Mob

Jumping Jack is in charge of organizing a flash mob. Themembers of the flash 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 flash mob’s members. Fortunately Jack has the locations of all themembers via the GPS on their cell phones. Your job is to find
the meetinglocation given all the members’ locations. Each intersection will be given by apair of non-negative integers; the first coordinate is the east-west street andthe second coordinate is the north-south street. The location of each flash 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, 5), and(5, 5). Then if Jack summons them all to location (3, 5), 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 first 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 firstcoordinate. If there is more than one ‘best’ location with the smallest firstcoordinate, 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 点的曼哈顿距离为：

由图可知：在a1，a2，a3，a4，a5 中选取a3点最好，即在[x1,x2]这个区间内选取a点最好，又因为题目中要求a最小，所以选a
= x2 是最佳的。

 

#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) %d\n" , ++ 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 ;
}