Hide

Problem B
巨人

Languages en ja sv

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

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

入力

入力の1行目には、洞窟の大きさを表すNM1N,M109)の2つの整数が含まれています。

2行目には、巨人の両足の座標を表す4つの整数 x1y1x2y2 (0x1,x2<N, 0y1,y2<M)が含まれています。 これらの点は常に異なります。

出力

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

採点

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

グループ

ポイント

制限

1

30

1N1000 and 1M1000

2

25

1000N109 and 1000M109

3

15

x1x2 and y1y2

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つの頂点が同じ直線状に載っていないことを表します。
Hide

Please log in to submit a solution to this problem

Log in