Demi-finale 2009, épreuve machine - Ne pas se rejeter dedans

DIFFICULTE

LIMITE DE MEMOIRE

8192 ko

LIMITE DE TEMPS

2000 ms

Attaqué par un tueur fou, Simon court vers sa voiture décapotable pour s'enfuir. L'endroit où il se trouve comporte une grande zone grillagée dans laquelle se trouvent plusieurs mares de mazout.

Simon n'a pas le temps de réfléchir et veut courir en ligne droite vers sa voiture. Vous devez lui dire s'il pourra y arriver ou s'il sera bloqué par le grillage.

Pour cela, l'on vous donne la position de Simon, la position de sa voiture, et la position de toutes les mares de mazout. Vous considérerez que le grillage est l'enveloppe convexe des mares, c'est à dire qu'il a été construit de façon à inclure dans son enceinte toutes les mares, tout en restant convexe et d'aire minimum comme sur cet exemple :

La première ligne contient deux entiers représentant la position de Simon sur la carte (ligne, colonne).
La ligne suivante contient deux entiers représentant la position de la voiture de Simon sur la carte (ligne, colonne). La ligne suivante contient un entier N, le nombre de mares de mazout. Les N lignes suivantes contiennent deux flottants représentant la position de la mare en question.

Un entier valant 1 si Simon peut atteindre sa voiture sans rencontrer les grillages autour du mazout, 0 sinon.

0 < N <= 100000.

EXEMPLE(S) D'ENTREE/SORTIE

Exemple 1
en entrée ...

10 0
10 10
7
6 5
8 4
9 5
9 7
12 4
12 6
13 7

0