Auf einer weiten Ebene grasen $N$ verstreute Ziegen. Keine zwei stehen an derselben Position. Die Ziegen sind faul: Sie bewegen sich nicht fort, sondern drehen sich nur gelegentlich auf der Stelle. Tatsächlich sind sie alle Roboter, die nicht laufen, sondern nur auf der Stelle rotieren können. Ihre Nasen sind fernsteuerbare LED-Leuchten und ihre Augen leistungsfähige Kameras, deren Bilder aus der Ferne in Echtzeit betrachtet und gespeichert werden können. Eine Ziege sieht ihre eigene Nase. Ihre Augen können außerdem durch andere Ziegen hindurchsehen, sodass sie auch bei überlappenden Ziegen deren Anzahl erkennt. Das horizontale Sichtfeld beträgt $180^\circ$ und schließt dessen Rand ein.

Je nach Anordnung können manche Ziegen alle $N$ Ziegen gleichzeitig sehen, während andere dies in keiner Blickrichtung können. Bei den sechs Ziegen mit Nummern $0$ bis $5$ in der Abbildung kann Ziege $5$ alle sechs gleichzeitig sehen, Ziege $2$ hingegen in keiner Blickrichtung.

Für ein besonderes Experiment werden zwei verschiedene Ziegen ausgewählt, die jeweils alle $N$ Ziegen gleichzeitig sehen können, und eine beliebige der übrigen Ziegen. Die Nasen dieser drei werden eingeschaltet, damit ihre Positionen von überall erkennbar sind. Aus den Augen jeder ausgewählten Ziege wird eine Szene gespeichert, in der alle drei leuchtenden Ziegen gleichzeitig im Bild sind. Die drei gespeicherten Szenen werden einzeln betrachtet. In jeder werden die drei leuchtenden Ziegen sowie alle Ziegen zwischen den beiden anderen leuchtenden Ziegen einschließlich der Begrenzungen besonders markiert. Ziel des Experiments ist es, unter den $N$ Ziegen diejenigen zu zählen, die in allen drei Szenen markiert werden.

Werden beispielsweise die drei aus sechs ausgewählten Ziegen als rote Punkte dargestellt, zeigen die folgenden Abbildungen die aus Sicht jeder ausgewählten Ziege markierten Ziegen. (Die Abbildungen sind nicht die gespeicherten Szenen selbst.) In diesem Fall werden $4$ Ziegen alle drei Male markiert.

Du musst für das Experiment die folgenden zwei Funktionen implementieren.

• void init( int x[], int y[] ): Diese Funktion wird zuerst und genau einmal aufgerufen. Die Arrays (Vektoren) x und y haben die Größe $N$. Die Argumente x[0..N-1] und y[0..N-1] enthalten die $x$- und $y$-Koordinaten der Ziegen. Ziege $i$ ($0\le i\le N-1$) steht bei (x[i], y[i]).
• int count( int a, int b, int c ): Berechnet anhand der Koordinaten (x[a], y[a]), (x[b], y[b]) und (x[c], y[c]) der drei angegebenen Ziegen die Anzahl der alle drei Male markierten Ziegen und gibt sie zurück.

Implementierungsdetails

Reiche eine einzige Datei namens goat.cpp ein, in der folgende Funktionen implementiert sind.

void init( int x[], int y[] );
int count( int a, int b, int c );

Die Funktionen müssen sich wie beschrieben verhalten. Du darfst weitere Funktionen für den internen Gebrauch definieren. Dein Code darf keine Ein-/Ausgabe ausführen und auf keine anderen Dateien zugreifen.

Beispiel für den Grader

Der bereitgestellte Grader liest die Eingabe in folgendem Format.

• Erste Zeile: $N\ Q$, wobei $N$ die Anzahl der Ziegen und $Q$ die Anzahl der Anfragen ist.
• Jede der nächsten $N$ Zeilen: $x\ y$, die $x$- und $y$-Koordinaten einer Ziege.
• Jede der nächsten $Q$ Zeilen: $a\ b\ c$ ($a,b,c$), die Nummern der drei Ziegen, wobei $0\le a,b,c\le N-1$ gilt.

Der Grader gibt für jede Anfrage die Anzahl der Ziegen aus, die die Bedingung erfüllen, jeweils in einer eigenen Zeile.

Beschränkungen

• $3\le N\le 3000$
• $1\le Q\le 5\times10^6$
• Alle $x$- und $y$-Koordinaten der Ziegen liegen zwischen $0$ und $10^9$ einschließlich.

Teilaufgaben

1 (5 Punkte)

• $N\le 500$, $Q\le 10^5$
• Keine drei Punkte liegen auf einer Geraden.

2 (17 Punkte)

• $N\le 500$, $Q\le 10^5$

3 (10 Punkte)

• $N\le 500$
• Keine drei Punkte liegen auf einer Geraden.

4 (8 Punkte)

• $N\le 500$

5 (29 Punkte)

• Keine drei Punkte liegen auf einer Geraden.

6 (31 Punkte)

• Keine weiteren Beschränkungen.

Beispiele

Eingabe 1

6 3
0 0
1 1
2 2
4 3
0 2
2 0
0 5 2
1 3 4
4 1 5

Ausgabe 1

4
4
3

Die Funktionsaufrufe und Ergebnisse für Beispiel 1 sind unten in ihrer Reihenfolge aufgeführt.