Programmeringsolympiadens final 2019

Start

2019-01-18 08:10 UTC

Programmeringsolympiadens final 2019

End

2019-01-18 13:10 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -303 days 11:41:51

Time elapsed

5:00:00

Time remaining

0:00:00

Problem B
Jätten

Du har blivit tillfångatagen av en ond jätte. Ni befinner er båda i en $N \times M$ stor grotta bestående av alla punkter $(x, y)$ med $0 \le x < N, 0 \le y < M$. Jätten tänker äta upp dig, så du måste rymma innan det är för sent! Jätten står med sina fötter på två olika punkter i grottan med heltalskoordinater. Du kan lägga en guldklimp på en tredje punkt i grottan. Jätten kommer då böja sig ner och försöka plocka upp guldklimpen. Om positionerna för jättens fötter samt guldklimpens position tillsammans bildar en trubbvinklig triangel kommer jätten tappa balansen och trilla. I så fall får du chansen att fly!

Skriv ett program som givet storleken på grottan, koordinaterna för jättens högra fot, $x_1, y_1$, samt koordinaterna för jättens vänstra fot, $x_2, y_2$, hittar en ny punkt med heltalskoordinater att lägga guldklimpen på, så att de tre punkterna bildar en icke-degenererad1 trubbvinklig triangel.

Indata

Den första raden består av två heltal, $N$ och $M$ ($1\leq N, M \leq 10^9$), grottans storlek.

Den andra raden består av 4 heltal, $x_1$, $y_1$, $x_2$ och $y_2$ ($0\leq x_1, x_2 < N$, $0\leq y_1, y_2 < M$), koordinaterna för jättens två fötter. Dessa punkter kommer alltid att vara olika.

Utdata

Skriv ut två heltal $x_3, y_3$ ($0\leq x_3 < N$, $0\leq y_3 < M$) på samma rad, så att punkten med dessa koordinaterna tillsammans med de två punkterna i indatan bildar en icke-degenererad trubbvinklig triangel. Det är garanterat att en sådan punkt finns.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

$1$

$30$

$1\leq N \leq 1000$ och $1\leq M \leq 1000$

$2$

$25$

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

$3$

$15$

$x_1 \neq x_2$ och $y_1 \neq y_2$

$4$

$30$

Inga ytterligare begränsningar

Förklaring av exempelfall 1

I exempelfall 1 bildar punkterna $(1,1)$, $(3,4)$ och $(1,2)$ en trubbvinklig triangel med trubbig vinkel vid $(1,2)$. $(1,2)$ ligger dessutom i grottan. Punkten $(1,4)$ hade inte varit en korrekt lösning eftersom triangeln som bildats då hade varit rätvinklig och inte trubbig. Punkten $(5,7)$ hade inte heller varit en lösning eftersom triangeln som bildats då hade varit degenererad, och $(5,7)$ dessutom ligger utanför grottan.

Sample Input 1 Sample Output 1
4 5
1 1 3 4
1 2
Sample Input 2 Sample Output 2
1000 1000
500 500 500 502
498 498
Sample Input 3 Sample Output 3
1000000000 1000000000
0 0 0 999999999
10 500000000

Footnotes

  1. En triangel är icke-degenererad om inte alla hörn ligger på en linje. https://en.wikipedia.org/wiki/Degeneracy_(mathematics)