Problem D
Dela ankor lika

Som en nådig härskare över POland vill du att alla dina invånare ska trivas. Det är därför djupt bekymrande att två barn bråkar. Mer exakt bråkar de över $2N$ kodsportsankor som ligger utplacerade på ett plan, och barnen grälar över hur många ankor var och en ska få.

För att lösa konflikten ska du skapa en spricka i marken - en rak linje som delar planet i två delar. Sprickan måste placeras så att exakt $N$ ankor hamnar på vardera sida, vilket då leder till att vardera barn får lika många ankor. Varje anka är utplacerad på en heltalskoordinat.

Eftersom du föredrar enkelhet och elegans kommer din spricka att vara en rät linje på formen $y=kx+m$, där $k$ och $m$ får vara decimaltal.
Om det finns en linje som delar ankorna lika, skriv ut denna.
Skriv annars ut ”impossible”.

Indata

Den första raden innehåller ett heltal $N$ ($1 \leq N \leq 10^5$), där $2N$ är det totala antalet ankor.

De följande $2N$ raderna beskriver ankornas positioner. Varje rad innehåller två heltal $x_i, y_i$ ($0 \leq x_i, y_i \leq 10^6$), koordinaterna för den $i$:te ankan. Alla ankor har olika positioner.

Utdata

Om det är möjligt att dela ankorna lika, skriv ut två reella tal $k$ och $m$ ($-5 \cdot 10^9 \leq k, m \leq 5 \cdot 10^9$) som beskriver linjen $y = kx + m$. $k$ och $m$ får innehålla som mest 50 tecken vardera. Domaren kommer att utföra alla beräkningar med $k$ och $m$ exakt. Notera att ditt program kan avrunda $k$ och $m$ när de skrivs ut.
Svaret accepteras om linjen delar ankorna i två lika stora grupper. Om det finns flera lösningar kan du skriva ut vilken som helst.
Om en anka befinner sig exakt på linjen kommer det att räknas som att den är under linjen.

Om det är omöjligt att dela ankorna lika, skriv ut ”impossible”.

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.

Förklaring av exempelfall

I varje av följande bilder har alla ankor ritats ut med svarta prickar. Sprickan som används i exempellösningen ritas ut som en röd linje. Notera att det finns flera giltiga lösningar i alla dessa fallen.

Figure 1: Bilden föreställer det första exempelfallet.

Figure 2: Bilden föreställer det andra exempelfallet. Det är svårt att se, men den andra punkten är precis under linjen.

Figure 3: Bilden föreställer det tredje exempelfallet.

1
1 1
0 0

-1 1

2
0 4
5 4
2 2
1 4

-3 7.00001

29
11 21
12 22
13 23
14 23
15 23
16 23
17 22
18 21
18 20
19 19
19 18
19 17
19 16
18 15
18 14
17 13
18 13
19 13
20 13
21 13
22 13
23 13
24 14
25 14
24 13
24 12
23 11
22 10
21 9
20 8
19 7
18 7
17 7
16 7
15 7
14 7
13 7
12 7
11 8
10 9
10 10
10 11
10 12
11 13
12 14
13 14
14 15
15 16
14 17
13 17
12 17
11 17
10 17
9 17
8 17
10 18
11 19
11 20

2.5 -24.9