#P13080. [NOISG 2017] Best Places / 最佳选址

    ID: 12710 Type: RemoteJudge 1000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 2 Uploaded By: Tags>贪心2017Special Judge排序NOISG(新加坡)

[NOISG 2017] Best Places / 最佳选址

题目背景

译自 NOISG 2017 A.Best Places

题目描述

IOI 2020 将在新加坡举行!举办这样的国际赛事,选择举办地自然成了十分重要的事。

现在,组委会拿到了一份选手住址名单,共有 NN 位选手,他们所在的城市可以看作一个坐标系,第 ii 位选手住在 (Xi,Yi)(X_i,Y_i)

为了选手们方便参加比赛,组委会想要选择一个点 (X,Y)(X,Y),使得所有 XXi+YYi|X-X_i|+|Y-Y_i| 之和最小。

请你输出这个 (X,Y)(X,Y)。如果有多种可能的答案,输出任意一个即可。

注意:最终答案 (X,Y)(X,Y) 可能与某个 (Xi,Yi)(X_i,Y_i) 相同。一个 (Xi,Yi)(X_i,Y_i) 点上也可能不止一位选手。你应该认为住在同一个点的选手分别单独去赛场,而不是将他们视为同一个人。

输入格式

第一行一个正整数 NN

接下来 NN 行,每行两个整数 Xi,YiX_i,Y_i

输出格式

一行两个整数 X,YX,Y

2
1 0
4 0
3 0
6
1 0
3 0
5 0
7 0
9 0
11 0

7 0
9
1 16
3 12
5 6
7 10
9 8
11 4
13 14
15 2
17 18

9 10

提示

【样例解释】

对于样例一,不难发现 (1,0),(2,0),(4,0)(1,0),(2,0),(4,0) 也是正确的输出。无论选择 (1,0),(2,0),(3,0)(1,0),(2,0),(3,0) 还是 (4,0)(4,0),都有 i=1N(XXi+YYi)=3\sum\limits_{i=1}^N(|X-X_i|+|Y-Y_i|)=3。可以证明没有 (X,Y)(X,Y) 可以使 XXi+YYi|X-X_i|+|Y-Y_i| 之和更小。

对于样例二,(5,0),(6,0)(5,0),(6,0) 也是正确的输出。

对于样例三,可以证明这是唯一正确的输出。

【数据范围】

本题采用 Subtask\text{Subtask} 捆绑测试。

Subtask\text{Subtask} 分值 NN Xi,YiX_i,Y_i
11 33 N=2N=2 0Xi,Yi1090\le X_i,Y_i\le10^9
22 2020 2N10002\le N\le1000 0Xi1000,Yi=00\le X_i\le1000,Y_i=0
33 2828 2N1062\le N\le10^6 0Xi109,Yi=00 \le X_i\le10^9,Y_i=0
44 1313 2N1002\le N\le100 0Xi,Yi1000\le X_i,Y_i\le100
55 1717 2N10002\le N\le1000 0Xi,Yi1090\le X_i,Y_i\le10^9
66 1919 2N1062\le N\le10^6

对于 100%100\% 的数据,2N1062\le N\le10^60Xi,Yi1090\le X_i,Y_i\le10^9