Hide

Problem B
巨人

あなたは、邪悪な巨人に捕まってしまいました。 あなたは、$N \times M$の広さの巨大な洞窟にいます。 洞窟内のすべての位置は整数座標$(x, y)$で表され、$0 \le x < N, 0 \le y < M$です。 巨人はあなたを食べるつもりなので、手遅れになる前に逃げなければなりません! 巨人は、洞窟の中の異なる2点に足を置いて立っています。 あなたは逃げるために、洞窟の第3のポイントに金の延べ棒を置くことを考えました。 そうすれば、巨人は身をかがめて金塊を拾い上げようとします。 巨人の足の位置と金の延べ棒の位置によってできる三角形が鈍角三角形になると、巨人はバランスを崩して倒れてしまいます。 その結果、逃げる機会を得ることができます。

洞窟の大きさ、巨人の右足の座標($x_1, y_1$)、左足の座標($x_2, y_2$)が与えられたとき、 非退化1鈍角三角形を構成する金の延べ棒を置く位置を表す整数座標を見つけるプログラムを書いてください。

入力

入力の1行目には、洞窟の大きさを表す$N$$M$$1\leq N, M \leq 10^9$)の2つの整数が含まれています。

2行目には、巨人の両足の座標を表す4つの整数 $x_1$$y_1$$x_2$$y_2$ ($0\leq x_1, x_2 < N$, $0\leq y_1, y_2 < M$)が含まれています。 これらの点は常に異なります。

出力

入力の2つの点とともに非退化鈍角三角形を形成する点の座標を表す2つの整数$x_3, y_3$ ($0\leq x_3 < N$, $0\leq y_3 < M$)を同じ行に出力します。 入力は、少なくとも1つはそのような点が存在するように構成されています。

採点

あなたのソリューションは、一連のテストケースグループでテストされます。 グループのポイントを得るためには、グループ内のすべてのテストケースに成功する必要があります。

グループ

ポイント

制限

$1$

$30$

$1\leq N \leq 1000$ and $1\leq M \leq 1000$

$2$

$25$

$1000\leq N\leq 10^9$ and $1000\leq M \leq 10^9$

$3$

$15$

$x_1 \neq x_2$ and $y_1 \neq y_2$

$4$

$30$

No further constraints

サンプル1の説明

例1では、3点$(1,1)$$(3,4)$$(1,2)$が、頂点$(1,2)$が鈍角となる鈍角三角形を構成します。$(1,2)$は洞窟内に含まれます。

座標$(1,4)$は正しい解ではありません。なぜなら、この3点では鋭角三角形を構成するからです。

座標$(5,7)$も正しい解ではありません。なぜなら、この3点では鈍角三角形を構成するものの、$(5,7)$は洞窟に含まれないからです。

サンプル入力 1 サンプル出力 1
4 5
1 1 3 4
1 2
サンプル入力 2 サンプル出力 2
1000 1000
500 500 500 502
498 498
サンプル入力 3 サンプル出力 3
1000000000 1000000000
0 0 0 999999999
10 500000000

Footnotes

  1. 三角形が非退化というのは、3つの頂点が同じ直線状に載っていないことを表します。
CPU Time limit 1 second
Memory limit 1024 MB
Languages English, 日本語, Svenska
Author
Erik Amirell Eklöf
Source Programmeringsolympiadens final 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in