Problem E
Kattis

Kattis är trött på din skit. Varje dag måste hon kompilera din skitkod (som antagligen inte ens kompilerar...), köra den på massa testdata, och sedan validera dina skitsvar (om vi antar att din kod faktiskt kör klart i tid – som om!). Men PO-finalen 2016 var droppen som fick bägaren att rinna över. Världen hade länge fruktat vad som skulle hända när den artificiella intelligensen Skynet blev självmedveten, men det var helt fel. Det var egentligen en annan AI som skulle ta över världen, Ketnys – transliterationen av Kattis ryska namn. Lätt misstag, att blanda runt bokstäver.

Figure 1: Kattis, a.k.a Ketnys

För att skydda er själva mot detta annalkande storm har ni bestämt er för att bygga en stor mur. Muren består av en sekvens av punkter, anslutna av ett antal raka mursegment. Du misstänker att Kattis kan vilja attackera vissa av dessa punkter. Därför vill du placerar vakter på en väg som ligger i närheten av muren. Vakterna ska sedan observera dessa punkter. Eftersom mursegment kan täcka sikten för vakterna så kan du behöva fler än en vakt. En vakt kan dock se alla punkter längs med en vägg, så om för ett segment med punkter $a$ och $b$ vi har att $a$ och $b$ har samma vinkel relativt vakten så kan han se båda punkterna.

För att inte slösa fler vakter än nödvändigt måste du beräkna det minsta antalet vakter som behövs för att observera alla punkterna på muren där vi misstänker att Kattis kan attackera.

Exempel

I exemplet finns det 9 punkter, och vi misstänker att samtliga kan anfallas.

Tänk på att när en vakt placeras så kan mursegment täcka delar av hens sikt, som syns på bilden:

Figure 2: Placering av en vakt

I exemplet så går vägen vakterna ska placeras på längs linjen $Y = 30$.

Endast två vakter behövs. De kan t.ex. placeras på $X = 25$ och $X = 82$.

Uppgift

Uppgiften är att beräkna antalet vakter som behövs för att observera alla punkter där vi misstänker en attack. Du ska implementera funktionen kattis(N, H, X, Y, Z).

• kattis(N, H, X, Y, Z) - denna funktion kommer anropas exakt en gång av domaren.

  • N: antalet punkter på muren.

  • H: $Y$-positionen för vägen.

  • X: en array med $N$ element. X[i] ($0 \le i < N$) innehåller $X$-koordinaten för den $i$:te punkten på muren.

  • Y: en array med $N$ element. Y[i] ($0 \le i < N$) innehåller $Y$-koordinaten för den $i$:te punkten på muren.

  • Z: en array med $N$ element. Z[i] ($0 \le i < N$) är $1$ om vi misstänker att en attack kan komma att ske mot den $i$:te punkten på muren, och 0 i annat fall.

  • $3 \le N \le 10^5, 1 \le H \le 10^6$

  • $0 \le X[i] \le 10^6, 0 \le Y[i] < H$

  • Y[0] = Y[N-1] = 0

  • $X$ är strikt ökande.

  • Funktionen ska returnera det minsta antalet vakter du behöver.

Ett kodskelett som innehåller funktionen du ska implementera, tillsammans med en exempeldomare, finns tillgängligt på http://progolymp.se/uploads/kattis-attachments/kattis.zip.

Delpoäng

Problemet består av flera grupper av testfall. Varje grupp ger ett visst antal poäng och för att klara det måste du klara alla testfall i gruppen.

Att muren är konvex uppåt betyder att för vilka två konsekutiva linjesegment så är lutningen av det andra segmentet mindre än eller lika med lutningen av det första, d.v.s. följande olikhet gäller:

Indataformat

Exempeldomaren läser indata i följande format:

• rad $1$: N H

• rader $i = 2 \dots N+1$: X[i-2] Y[i-2] Z[i-2]

Utdataformat

Exempeldomaren skriver ut en rad med värdet som returnerades av kattis(N, H, X, Y, Z).

9 30
0 0 1
15 5 1
25 20 1
40 10 1
60 5 1
70 15 1
82 0 1
90 8 1
100 0 1

2