HDU 1173 思路题

题目大意

有n个地点（坐标为实数）需要挖矿，让选择一个地点，使得在这个地方建造基地，到n个地点的距离和最短，输出基地的坐标。

题解+代码：

 1 /*
 2 把这个二维分开看（即把所有点投影到x轴上，再把所有点投影到y轴上），毕竟走的时候只能向上下或者向左右走
 3 
 4 这里以投影到x轴上为例，设这些点是a1...an，且是排过序的（这里以升序为例）
 5 当n==2的时候，那么在区间[a1,a2]上的任意一个点都可以满足题意，例如a1=1,a2=2的时候，你取1.5或1.6或1.7......
 6 你到达这2个地址的路程之和都一样
 7 
 8 n大于2的时候，答案应该满足在[x1,xn],[x2,xn-1]…上，依次往后推。
 9 
10 如果n是奇数就是在中间的点上，如果是偶数，就是中间的一个线段上。
11 
12 不论奇数偶数，中间点一定是最短的。
13 */
14 #include<stdio.h>
15 #include<string.h>
16 #include<iostream>
17 #include<algorithm>
18 #include<queue>
19 #include<vector>
20 using namespace std;
21 const int maxn=1e6+10;
22 const int INF=0x3f3f3f3f;
23 typedef long long ll;
24 double arr[maxn],brr[maxn];
25 int main()
26 {
27     int n;
28     while(~scanf("%d",&n)&&n)
29     {
30         for(int i=1; i<=n; i++)
31             scanf("%lf%lf",&arr[i],&brr[i]);
32         sort(arr+1,arr+1+n);
33         sort(brr+1,brr+1+n);
34         printf("%.2lf %.2lf
",arr[n/2], brr[n/2]);
35     }
36     return 0;
37 }