AT_arc047_b.[ARC047B] 同一円周上

省选/NOI-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

在坐标平面上有 NN 个点。

这些点的 xx 坐标和 yy 坐标都是整数,也就是说它们都在格点上。

此外,这些点都与某个点 PP 的曼哈顿距离相同。这里,曼哈顿距离指的是,对于两个点的坐标分别为 (a, b), (c, d)(a,\,b),\ (c,\,d) 时,距离为 ∣a−c∣+∣b−d∣|a-c|+|b-d|。

并且,点 PP 也在格点上。

请给出一个可能作为点 PP 的点。

输入格式

输入通过标准输入给出,格式如下:

NN
x1x_1 y1y_1
x2x_2 y2y_2
⋮\vdots
xNx_N yNy_N

  • 第 11 行是一个整数 NN,表示点的个数,1≤N≤1051 \leq N \leq 10^5。
  • 接下来的 NN 行中,第 ii 行包含两个整数 xi, yix_i,\,y_i,表示第 ii 个点的坐标,−109≤xi, yi≤109-10^9 \leq x_i,\,y_i \leq 10^9。
  • 若 i≠ji \neq j,则 (xi, yi)≠(xj, yj)(x_i,\,y_i) \neq (x_j,\,y_j)。
  • 保证这 NN 个点一定都与某个点的曼哈顿距离相等。

输出格式

请输出一个可能作为点 PP 的点的 xx 坐标 PxPx 和 yy 坐标 PyPy,用空格隔开,输出一行。

要求 −109≤Px, Py≤109-10^9 \leq Px,\,Py \leq 10^9(保证一定存在这样的解)。

输出末尾需换行。

输入输出样例

  • 输入#1

    3
    1 2
    3 4
    2 5

    输出#1

    2 3
  • 输入#2

    3
    0 1
    1 0
    -1 0

    输出#2

    0 -2016

说明/提示

样例解释 1

给出的所有点到点 (2, 3)(2,\,3) 的曼哈顿距离都是 22。

样例解释 2

所有满足 y≤0y \leq 0 的点 (0, y)(0,\,y) 都可以作为点 PP。在这种情况下,只要 −109≤y-10^9 \leq y,输出任意一个都可以。

由 ChatGPT 4.1 翻译

输入解题思路,AI测评打分。不知道怎么写?

首页