Flash Mob

Description
Jumping Jack is in charge of organizing a ash mob. The members of the ash mob move around town all day and part of the appeal of this group 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 at a particular intersection in town in exactly one hour. The streets of the town run only north-south or east-west and are evenly spaced, forming a perfect grid like a sheet of graph paper. Due to the spontaneity, Jack wants to minimize the inconvenience and so picks an intersection to minimize the total distance traveled by the ash mob’s members. Fortunately Jack has the locations of all the members via the GPS on their cell phones. Your job is to second the meeting location given all the members’ locations. Each intersection will be given by a pair of non-negative integers; the first coordinate is the east-west street and the second coordinate is the north-south street. The location of each ash mob member will be an intersection. Members can travel only north-south or east-west between 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 of blocks traveled by the mob members would be 14. Jack could do no better { but sometimes the ‘best’ location may not be unique

Input

Input for each test case will be a 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 integers indicating the location (intersection) of each member. The location coordinates are both between 0 and 10^6, inclusive. More than one member may be at the same intersection. A line containing 0 will follow the last test case.

Output

Output one line for each test case in the format given below. The ordered pair is the coordinates of the location 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 first coordinate. If there is more than one ‘best’ location with the smallest first coordinate, output the one of those with the smallest second coordinate. The total 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

Source

2012 East Central Regional Contest

//求平面上一点到其他点曼哈顿距离和最小
//其实只要分别考虑两维就好了
//y=|x-x1|+|x-x2|+...+|x-xn|，的最小值一定取在中位数值上(包括偶数个点，此时中间是水平线)
//但是下面的算法并不是这么求的，用的模拟退火的方法，也刷到了8ms，挺不容易的。当然上面的算法肯定是0ms了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int p[1005][3],n;
int px[1005],py[1005];
//int min_x,min_y,max_x,max_y;
int st_x,st_y;
int st;
int multx,multy;
const int dx[]={-1,-1,0,-1,0,1,1,1};
const int dy[]={-1,0,-1,1,1,-1,0,1};
 
inline int Abs(int x)
{
    if(x>0)return x;
    return -x;
}
 
int sum(int x,int y)
{
    int ret=0;
    for(int i=0;i<n;i++)
      ret+=Abs(p[i][0]-x)+Abs(p[i][1]-y);
    //cout<<"sum "<<x<<" "<<y<<" "<<ret<<endl;
    //cout<<ret<<endl;
    return ret;
}
 
void solve()
{
    //st_x=(min_x+max_x)/2;st_y=(min_y+max_y)/2;
    int stx,sty;
    int idx;
    st=sum(st_x,st_y);
    int st2;
    while(1)
    {
        idx=-1;
        for(int i=0;i<8;i++)
        {
            stx=st_x+multx*dx[i];
            sty=st_y+multy*dy[i];
            st2=sum(stx,sty);
            if(st2<st || (i<3 && st2==st))
            {
                st=st2;
                idx=i;
            }
        }
        if(-1==idx)
        {
            if(1==multx && 1==multy)break;
            if(multx>1)multx>>=1;
            if(multy>1)multy>>=1;
        }
        else
        {
            st_x=st_x+multx*dx[idx];
            st_y=st_y+multy*dy[idx];
        }
        //cout<<idx<<" "<<st_x<<" "<<st_y<<" "<<sum(st_x,st_y)<<endl;
       //system("pause");
    }
}
 
int main()
{
    freopen("1796in.txt","r",stdin);
    freopen("1796_revise_out.txt","w",stdout);
    int tx,ty;
    long long sx,sy;
    int cs=0;
    while(scanf("%d",&n),n)
    {
        //min_x=1e6;min_y=1e6;
        //max_x=0;max_y=0;
        sx=0;sy=0;
        for(int i=0;i<n;i++)
        {
            //cin>>tx>>ty;
            scanf("%d%d",&tx,&ty);
            p[i][0]=tx;p[i][1]=ty;
            px[i]=tx;py[i]=ty;
            sx+=tx;
            sy+=ty;
        }
        sort(px,px+n);
        sort(py,py+n);
        multx=(px[n-1]-px[0])/2;
        multy=(py[n-1]-py[0])/2;
        if(n&1)
        {
            st_x=px[n/2];
            st_y=py[n/2];
        }
        else
        {
            st_x=(px[n/2]+px[n/2+1])/2;
            st_y=(py[n/2]+py[n/2+1])/2;
        }
        solve();
        cs++;
        //cout<<"Case "<<cs<<": ("<<st_x<<","<<st_y<<") "<<st<<endl;
        printf("Case %d: (%d,%d) %dn",cs,st_x,st_y,st);
    }
    return 0;
}