Descriere

Implementați un algoritm care să verifice dacă o muchie a unei triangulări este legală. Puteți folosi folosi problema 1 , bazată pe criteriul geometric/numeric descris în cursul 10.

Date de intrare

Programul va citi de la tastatură patru perechi de numere întregi separate prin spațiu \(x_i \, y_i\), pe linii distincte, reprezentând coordonatele vârfului \(P_i (x_i, y_i)\) al patrulaterului. Vârfurile sunt date în sens trigonometric, iar patrulaterul este convex.

Date de ieșire

Programul va afișa pe ecran două rânduri, pe primul aflându-se șirul de caractere AC:, urmat de un spațiu și apoi cuvântul LEGAL sau ILLEGAL; iar pe al doilea, șirul de caractere BD:, urmat de un spațiu și apoi cuvântul LEGAL sau ILLEGAL.

Primul rând indică dacă muchia \(AC\) este legală, iar al doilea rând indică dacă muchia \(BD\) este legală.

Restricții și precizări

• \(-10^6 \leq x, y \leq 10^6\)

Exemplu

Input

-2 4
-3 0
0 -2
1 2

Output

AC: ILLEGAL
BD: LEGAL

Explicație

Coordonatele de mai sus corespund următorului poligon:

Folosind criteriul geometric observăm că:

• Punctul \(D\) este în interiorul cercului circumscris triunghiului \(\Delta ABC\), deci muchia \(AC\) este ilegală.
• Punctul \(A\) este în exteriorul cercului circumscris triunghiului \(\Delta BCD\), deci muchia \(BD\) este legală.