Flash Mob

发布时间：2020-12-15 18:17:27 所属栏目：百科来源：网络整理

导读：题目链接：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblemproblemid=1944 题目大意：找出一个使其到给出的所有的点距离最短题目思路：点肯定存在在所有点的中间位置，从中间位置比较找出该点题目： Flash Mob Time Limit: 1000MS Memory

题目链接：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1944

题目大意：找出一个使其到给出的所有的点距离最短

题目思路：点肯定存在在所有点的中间位置，从中间位置比较找出该点

题目：

Flash Mob

Time Limit: 1000MS Memory limit: 65536K

题目描述

Jumping Jack is in charge of organizing a flash mob. The members of the flash 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 flash mob’s members. Fortunately Jack has the locations of all the members via the

GPS on their cell phones. Your job is to find 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 flash 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,and (5,5). Then if Jack summons them all to location (3,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 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 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.

示例输入

5 3 4 0 5 1 1 5 5 5 5
4 100 2 100 2 100 2 1 20000
0

示例输出

Case 1: (3,5) 14
Case 2: (100,2) 20097

代码：

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
struct node
{
    int x;
    int y;
} point[1005];
int main()
{
    int n;
    int num=0;
    int x,y;
    while(scanf("%d",&n))
    {
        if(n==0)
            break;
        num++;
        x=0;
        y=0;
        for(int i=0; i<n; i++)
        {
            cin>>point[i].x>>point[i].y;
            x+=point[i].x;
            y+=point[i].y;
        }
        x/=n;
        y/=n;
        int ansx,ansy,dansx,dansy;
        int tmp,d;
        dansx=0;
        for(int i=0; i<n; i++)
        {
            dansx+=fabs(point[i].x-x);
        }
        ansx=x;
        tmp=x;
        while(true)
        {
            tmp--;
            d=0;
            for(int i=0; i<n; i++)
            {
                d+=fabs(point[i].x-tmp);
            }
            if(d>dansx)
                break;
            dansx=d;
            ansx=tmp;
        }
        tmp=x;
        while(true)
        {
            tmp++;
            d=0;
            for(int i=0; i<n; i++)
            {
                d+=fabs(point[i].x-tmp);
            }
            if(d>=dansx)
                break;
            dansx=d;
            ansx=tmp;
        }
        dansy=0;
        for(int i=0; i<n; i++)
        {
            dansy+=fabs(point[i].y-y);
        }
        ansy=y;
        tmp=y;
        while(true)
        {
            tmp--;
            d=0;
            for(int i=0; i<n; i++)
            {
                d+=fabs(point[i].y-tmp);
            }
            if(d>dansy)
                break;
            dansy=d;
            ansy=tmp;
        }
        tmp=y;
        while(true)
        {
            tmp++;
            d=0;
            for(int i=0; i<n; i++)
            {
                d+=fabs(point[i].y-tmp);
            }
            if(d>=dansy)
                break;
            dansy=d;
            ansy=tmp;
        }
        printf("Case %d: (%d,%d) %dn",num,ansx,dansx+dansy);
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!