← 返回题目列表

AtCoder · past21_o

O. 曼哈顿绳

中文机器翻译题面 查看原题

问题陈述

考虑放置 N 点 \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\} 在二维平面上满足以下条件:

  • 对于所有 i=1,2,\dots,N, 曼哈顿距离 点之间 (x_i,y_i) 和 (a_i,b_i) 最多是 d_i.
  • 对于所有 j=1,2,\dots,M,点之间的曼哈顿距离 (x_{u_j},y_{u_j}) 和 (x_{v_j},y_{v_j}) 最多是 e_j.

这里,两点之间的曼哈顿距离 (p_1,q_1) 和 (p_2,q_2) 定义为 |p_1-p_2|+|q_1-q_2|。注意坐标 x_i 和 y_i 不一定是整数。

判断是否存在这样的放置 N (不一定不同)点。如果存在,求原点之间最大可能的曼哈顿距离 (0,0) 和点 (x_P,y_P)。 在该问题的约束下,可以证明答案是整数,因此将答案打印为整数。

约束

  • 1 \leq N \leq 2000
  • 0 \leq M \leq \min\{2000, N(N-1)/2\}
  • 1 \leq P \leq N
  • |a_i|,|b_i|\leq 10^8
  • 0 \leq d_i\leq 10^8
  • 1 \leq u_j < v_j\leq N
  • If j\neq k,然后 (u_j,v_j) \neq (u_k,v_k).
  • 0 \leq e_j\leq 10^8
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M P
a_1 b_1 d_1
a_2 b_2 d_2
\vdots
a_N b_N d_N
u_1 v_1 e_1
u_2 v_2 e_2
\vdots
u_M v_M e_M

输出

打印 -1 如果没有符合要求的放置。

如果有,则打印原点之间最大可能的曼哈顿距离 (0,0) 和点 (x_P,y_P) 作为整数。


示例输入 1

1 0 1
1 1 2

示例输出 1

4

该样本的设置如下图所示。 圆圈表示点 (a_1,b_1),正方形表示满足的区域 |x-a_1|+|y-b_1|\leq d_1。 例如,通过放置 (x_1,y_1) at (2,2) (图中的星星),曼哈顿距离 (x_1,y_1) 和原点可以是 4.

或者,放置 (x_1,y_1) at (1.5, 2.5) 也满足条件,导致曼哈顿距离为 4.


示例输入 2

2 1 2
1 1 2
-2 2 3
1 2 1

示例输出 2

3

例如,通过放置 (x_1,y_1) at (0,2) 和 (x_2,y_2) at (-1,2),所有条件都可以满足。 在这种情况下,曼哈顿距离 (x_2,y_2) 的原点是 3,这是最大可能的。


示例输入 3

2 1 1
2 0 1
-2 0 1
1 2 1

示例输出 3

-1

无论你放在哪里 (x_1,y_1) 和 (x_2,y_2) 分别在蓝色和橙色区域,它们之间的曼哈顿距离永远不可能 1.