$N$ chèvres sont dispersées dans une vaste plaine et broutent tranquillement. Aucune paire n’occupe la même position. Elles sont paresseuses : elles ne se déplacent pas, mais tournent parfois sur place. En réalité, ce sont toutes des robots incapables de marcher, qui peuvent seulement pivoter sur place. Leurs nez sont des LED que l’on peut allumer à distance, et leurs yeux des caméras performantes dont on peut regarder les images à distance en temps réel et enregistrer des scènes. Une chèvre voit son propre nez. Ses yeux voient aussi à travers les autres chèvres, lui permettant d’en connaître le nombre même lorsqu’elles se superposent dans l’image. Le champ de vision horizontal est de $180^\circ$, frontières comprises.

Selon leurs positions, certaines chèvres voient les $N$ chèvres en même temps, tandis que d’autres ne le peuvent dans aucune direction. Par exemple, parmi les six chèvres numérotées de $0$ à $5$ ci-dessous, la chèvre $5$ voit les six simultanément, mais la chèvre $2$ ne le peut quelle que soit sa direction de regard.

Pour une expérience spéciale, on choisit deux chèvres distinctes capables chacune de voir les $N$ chèvres simultanément, ainsi qu’une chèvre quelconque parmi les autres. On allume les nez des trois chèvres choisies pour repérer leurs positions depuis n’importe où. On observe les images de leurs yeux et on enregistre pour chacune une scène où les trois chèvres éclairées apparaissent dans la même image. On examine les trois scènes une par une. Dans chacune, on marque spécialement les trois chèvres éclairées ainsi que toutes les chèvres situées entre les deux autres chèvres éclairées, frontières comprises. L’objectif est de compter, parmi les $N$ chèvres, celles qui sont marquées dans les trois scènes.

Par exemple, si les trois chèvres choisies parmi les six sont représentées par des points rouges, les figures suivantes montrent les chèvres marquées du point de vue de chacune. (Ces figures ne sont pas les scènes enregistrées elles-mêmes.) Dans ce cas, $4$ chèvres sont marquées les trois fois.

Vous devez implémenter les deux fonctions suivantes pour cette expérience.

• void init( int x[], int y[] ) : cette fonction est appelée en premier, exactement une fois. Les tableaux (vecteurs) x et y sont de taille $N$. Les arguments x[0..N-1] et y[0..N-1] donnent les coordonnées $x$ et $y$ des chèvres. La chèvre $i$ ($0\le i\le N-1$) est en (x[i], y[i]).
• int count( int a, int b, int c ) : à partir des coordonnées (x[a], y[a]), (x[b], y[b]) et (x[c], y[c]) des trois chèvres données, calcule et renvoie le nombre de chèvres marquées les trois fois.

Détails d'implémentation

Vous devez soumettre un seul fichier nommé goat.cpp, qui implémente les fonctions suivantes.

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

Ces fonctions doivent se comporter comme décrit ci-dessus. Vous pouvez définir d’autres fonctions à usage interne. Le code soumis ne doit effectuer aucune entrée/sortie ni accéder à d’autres fichiers.

Exemple d’évaluateur

L’évaluateur fourni lit l’entrée au format suivant.

• Première ligne : $N\ Q$, où $N$ est le nombre de chèvres et $Q$ le nombre de requêtes.
• Chacune des $N$ lignes suivantes : $x\ y$, les coordonnées $x$ et $y$ d’une chèvre.
• Chacune des $Q$ lignes suivantes : $a\ b\ c$ ($a,b,c$), les indices des trois chèvres, avec $0\le a,b,c\le N-1$.

Pour chaque requête, l’évaluateur affiche le nombre de chèvres satisfaisant la condition, sur une ligne distincte.

Contraintes

• $3\le N\le 3000$
• $1\le Q\le 5\times10^6$
• Les coordonnées $x$ et $y$ de toutes les chèvres sont comprises entre $0$ et $10^9$, bornes incluses.

Sous-tâches

1 (5 points)

• $N\le 500$, $Q\le 10^5$
• Aucun groupe de trois points n’est aligné.

2 (17 points)

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

3 (10 points)

• $N\le 500$
• Aucun groupe de trois points n’est aligné.

4 (8 points)

• $N\le 500$

5 (29 points)

• Aucun groupe de trois points n’est aligné.

6 (31 points)

• Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

4
4
3

Voici, dans l’ordre, les appels de fonctions et leurs résultats pour l’exemple 1.