题目背景
译自 NOISG 2017 A.Best Places。
题目描述
IOI 2020 将在新加坡举行!举办这样的国际赛事,选择举办地自然成了十分重要的事。
现在,组委会拿到了一份选手住址名单,共有 N 位选手,他们所在的城市可以看作一个坐标系,第 i 位选手住在 (Xi,Yi)。
为了选手们方便参加比赛,组委会想要选择一个点 (X,Y),使得所有 ∣X−Xi∣+∣Y−Yi∣ 之和最小。
请你输出这个 (X,Y)。如果有多种可能的答案,输出任意一个即可。
注意:最终答案 (X,Y) 可能与某个 (Xi,Yi) 相同。一个 (Xi,Yi) 点上也可能不止一位选手。你应该认为住在同一个点的选手分别单独去赛场,而不是将他们视为同一个人。
输入格式
第一行一个正整数 N。
接下来 N 行,每行两个整数 Xi,Yi。
输出格式
一行两个整数 X,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),(3,0) 还是 (4,0),都有 i=1∑N(∣X−Xi∣+∣Y−Yi∣)=3。可以证明没有 (X,Y) 可以使 ∣X−Xi∣+∣Y−Yi∣ 之和更小。
对于样例二,(5,0),(6,0) 也是正确的输出。
对于样例三,可以证明这是唯一正确的输出。
【数据范围】
本题采用 Subtask 捆绑测试。
Subtask |
分值 |
N |
Xi,Yi |
1 |
3 |
N=2 |
0≤Xi,Yi≤109 |
2 |
20 |
2≤N≤1000 |
0≤Xi≤1000,Yi=0 |
3 |
28 |
2≤N≤106 |
0≤Xi≤109,Yi=0 |
4 |
13 |
2≤N≤100 |
0≤Xi,Yi≤100 |
5 |
17 |
2≤N≤1000 |
0≤Xi,Yi≤109 |
6 |
19 |
2≤N≤106 |
对于 100% 的数据,2≤N≤106,0≤Xi,Yi≤109。