小 W, étudiant en génie logiciel, passe un examen de dessin technique. Il n'a apporté qu'une règle dont les graduations ont été effacées par le temps et un compas. À bout de ressources, il ne peut que faire appel à vos remarquables talents de construction géométrique. Aidez-le à réaliser ses constructions rapidement et précisément avec une règle non graduée et un compas.

Simplifions le problème : supposons que 小 W dispose déjà d'un repère et d'une longueur unité. Il vous demande de construire la longueur $L_0$, autrement dit d'obtenir le point $(L_0,0)$.

Vous pouvez effectuer les trois opérations suivantes :

1. $\operatorname{line}(A,B)$ : tracer la droite passant par les points $A$ et $B$ ;
2. $\operatorname{circle}(O,A,B)$ : tracer le cercle de centre $O$ dont le rayon est la distance $AB$ ;
3. $\operatorname{intersect}(i,j)$ : marquer tous les points d'intersection des figures $i$ et $j$. S'il y en a plusieurs, les marquer tous.

Initialement, 小 W vous fournit l'origine $O(0,0)$, qui est le point numéro $0$. Le point numéro $1$, de coordonnées $(1,0)$, donne la longueur unité. L'axe des $x$ (figure numéro $0$) et l'axe des $y$ (figure numéro $1$) sont également fournis.

Les nouveaux points et figures obtenus lors des opérations reçoivent les numéros suivants.

Si le numéro courant est $n$, le point produit par une opération $\operatorname{intersect}$ reçoit le numéro $n+1$.

Si les deux figures n'ont aucun point d'intersection, aucun nouveau point n'est produit.

S'il y a deux points d'intersection, celui dont l'abscisse $x$ est la plus petite (ou, en cas d'égalité, dont l'ordonnée $y$ est la plus petite) reçoit le numéro $n+1$ ; l'autre reçoit le numéro $n+2$.

Obtenez le point $(L_0,0)$ et indiquez son numéro. La valeur obtenue n'a pas besoin d'être exacte, mais votre score dépend de son écart à la valeur exacte et du nombre d'opérations utilisées.

Entrée

Il s'agit d'un problème où vous devez soumettre uniquement les réponses. Tous les fichiers d'entrée draw1.in à draw10.in se trouvent dans le répertoire du problème.

Chaque donnée d'entrée $x_0$ est une expression de calcul Python. L'opérateur ** représente une puissance : 3 ** 2 représente $3^2$, et 2 ** 0.5 représente $\sqrt2$.

Pour fournir une grande précision, les nombres de l'expression sont convertis au type decimal, c'est-à-dire en nombres décimaux de haute précision. Decimal(2) représente ainsi $2$.

Il est garanti qu'un espace sépare chaque nombre d'un symbole et chaque symbole du suivant.

La sortie du code Python est le nombre à construire.

Attention : un calcul direct en Python donne une approximation, alors que la valeur demandée est exacte. C'est donc à la valeur exacte que votre résultat sera comparé.

Nous fournissons aussi le fichier draw.pdf, qui présente les expressions de chaque jeu de données sous une forme facile à lire.

Sortie

Pour les 10 fichiers d'entrée draw1.in à draw10.in, vous devez soumettre respectivement les fichiers de sortie draw1.out à draw10.out.

La première ligne du fichier de sortie contient un entier $n$, le nombre d'opérations. Les $n$ lignes suivantes contiennent chacune une opération. Les formats des trois opérations sont :

line: L A B
circle: C O A B
intersect: I i j

Les paramètres ont le sens indiqué dans l'énoncé.

La dernière ligne du fichier de sortie contient un entier indiquant le numéro du point finalement obtenu.

Exemples

Entrée 1

Decimal( 2 ) ** ( Decimal( 1 ) / Decimal( 2 ) )

Sortie 1

5
C 0 0 1
I 1 2
C 0 1 3
L 1 3
I 0 3
5

Remarque

Les cinq opérations de l'exemple ont les significations suivantes :

1. Tracer un cercle de centre $O$ et de rayon égal à la longueur unité. Ce cercle est la figure numéro $2$.
2. Prendre les intersections de la figure numéro $2$ (le cercle) avec l'axe des $y$. Les points obtenus sont le point numéro $2$, de coordonnées $(0,-1)$, et le point numéro $3$, de coordonnées $(0,1)$.
3. Tracer un cercle de centre $O$, dont le rayon est la distance entre les points numéros $1$ et $3$. Ce cercle est la figure numéro $3$.
4. Relier les points $(1,0)$ et $(0,1)$. La droite obtenue est la figure numéro $4$.
5. Prendre les intersections de la figure numéro $3$ (le cercle) avec l'axe des $x$. Les points obtenus sont le point numéro $4$, de coordonnées $(-\sqrt2,0)$, et le point numéro $5$, de coordonnées $(\sqrt2,0)$.

Le point numéro $5$ est donc le point recherché.

Sous-tâches

Pour les 10 fichiers d'entrée draw1.in à draw10.in, nous fournissons respectivement les fichiers de paramètres de notation draw1.ans à draw10.ans.

Chaque fichier de paramètres contient dix lignes. Chaque ligne contient deux nombres $c_i,x_i$ : si la différence absolue entre l'abscisse $x$ du point final $(x,0)$ et $L_0$ ne dépasse pas $10^{-x_i}$, et si le nombre d'opérations utilisées satisfait $n\le c_i$, vous pouvez obtenir $i$ points.

Le score retenu est le plus élevé de ceux dont les conditions sont satisfaites. Si aucune condition n'est satisfaite, le score est $0$.

Comment tester votre sortie

Nous fournissons l'outil checker pour vérifier si votre fichier de sortie est acceptable. Ouvrez d'abord un terminal et exécutez la commande suivante pour entrer dans le dossier du problème :

cd draw

Exécutez ensuite :

./checker <case_no>

case_no est le numéro du jeu de données. Par exemple :

./checker 3

Cette commande teste si draw3.out est acceptable.

Après son exécution, checker indique le résultat du test pour votre fichier de sortie, notamment :

1. Fin anormale : erreur inconnue.
2. Invalid parameters for checker. : les paramètres transmis à checker sont invalides.
3. Input/Output file does not exist. : le fichier d'entrée ou de sortie n'existe pas.
4. Output invalid : le fichier de sortie est incorrect ; un message d'erreur détaillé peut être fourni.
5. Correct! Your answer is n. Your score is s. : la sortie est acceptable, le nombre d'opérations utilisées est $n$ et le score pour ce test est $s$.

Fonctionnalités supplémentaires

checker peut aussi tester des fichiers d'entrée et de sortie quelconques. Exécutez dans le terminal :

cd draw
./checker <input_file> <output_file> <ans_file>

input_file, output_file et ans_file sont respectivement les noms du fichier d'entrée, du fichier de sortie et du fichier de référence pour la notation.

Par exemple :

./checker draw3.in draw3.out draw3.ans

Cette commande teste si draw3.out est acceptable.

L'option -w affiche les coordonnées de chaque point créé. Chaque ligne de la sortie a le format :

id x y

Ces champs indiquent respectivement le numéro du point, sa coordonnée $x$ et sa coordonnée $y$. Utilisation :

./checker -w <input_file> <output_file> <ans_file>

ou :

./checker -w <case_no>

Par exemple :

./checker -w draw3.in draw3.out draw3.ans

L'option -i affiche également la sortie du participant pour faciliter le débogage. Utilisation :

./checker -i <input_file> <output_file> <ans_file>

ou :

./checker -i <case_no>

Par exemple :

./checker -i draw3.in draw3.out draw3.ans

L'option -e prec permet de fixer la précision des calculs de checker (le nombre de chiffres significatifs). Sans cette option, prec vaut $200$ par défaut. Utilisation :

./checker -e <prec> <input_file> <output_file> <ans_file>

ou :

./checker -e <prec> <case_no>

Par exemple :

./checker -e 50 draw3.in draw3.out draw3.ans

Les options -e prec, -w et -i peuvent être utilisées ensemble, dans n'importe quel ordre, par exemple :

./checker -w -i -e 50 draw3.in draw3.out draw3.ans

Remarque

Vous pouvez utiliser Python pour obtenir une approximation de l'expression. Lancez Python dans un terminal, puis saisissez :

from math import *
from decimal import *
getcontext().prec = 100

Copiez ensuite l'expression (le code Python) du fichier d'entrée dans ce terminal et appuyez sur Entrée pour obtenir une approximation de l'expression. Vous pouvez remplacer le nombre $100$ du code ci-dessus par la précision souhaitée.

Remarques particulières

Si vous utilisez vos propres fichiers d'entrée pour déboguer, une taille trop grande peut provoquer une erreur dans checker. Dans ce cas, essayez des données plus petites.

Conservez soigneusement les fichiers d'entrée draw.in, vos fichiers de sortie draw.out et les fichiers de paramètres de notation draw*.ans, et faites régulièrement des sauvegardes pour éviter toute suppression accidentelle.