F - F HDU - 1173(二维化一维-思维)

F - F HDU - 1173

一个邮递员每次只能从邮局拿走一封信送信。在一个二维的直角坐标系中，邮递员只能朝四个方向移动，正北、正东、正南、正西。

有n个需要收信的地址，现在需要你帮助找到一个地方建设邮局，使得邮递员送往n个地址的路程之和最短。

Input 多组输入，每组数据的第一行一个整数

n(0<n<1000000)，表示地址有n个。在接下来的n行中，每行有两个实数x,y，表示其中一个收信地址的坐标。n = 0时输入结束。

（实数范围原题没给出，c++ double存储够用，运算后自行避免精度问题）

Output 每组输入，输出两个实数x，y（保留两位），代表邮局位置。如果坐标不唯一输出其中一个最优解即可。

Sample Input

4

1.0 1.0

3.0 1.0

3.0 3.0

1.0 3.0

0

Sample Output

2.00 2.00

思路

分析：首先明白我们选的某个位置（x，y），无论在x轴方向，无论我们让x等于什么？都不会影响在y轴方向的总的最小和距离，同y坐标也不会影响在x轴方向的总水平和距离，剩下的就是单独讨论水平、竖直方向的情况

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<map>

#include<string>

#include<stack>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define INF 1e9

#define db double

const int Len = 1000005;

db x[Len];

db y[Len];

db Solve(db a[], int n)

{

    sort(a + 1, a + 1 + n);

    if(n % 2)

        return a[n/2 + 1];

    return (a[n/2] + a[n/2 + 1])/2;

}

int main()

{

    /* freopen("A.txt","r",stdin); */

    /* freopen("Ans.txt","w",stdout); */

    int n;

    while(scanf("%d", &n) && n)

    {

        for(int i = 1; i <= n; i ++)

            scanf("%lf %lf", &x[i], &y[i]);

        printf("%.2f %.2f\n", Solve(x, n), Solve(y, n));

    }

    return 0;

}

巴特西

F - F HDU - 1173(二维化一维-思维)

思路

代码

最新文章

热门文章