Segmente

Time limit: 0.3s Memory limit: 32MB Input: segmente.in Output: segmente.out

Se dă o mulțime de segmente. Segmentele sunt reținute prin cele două capete, iar capetele prin coordonatele lor carteziene. Un segment nu poate fi format dintr-un singur punct. Două segmente se consideră adiacente dacă ele au o extremitate comună.
Segmentele SiS_i și SjS_j se numesc conectate dacă există o succesiune de segmente, care începe cu SiS_i și se termină cu SjS_j, în care două segmente consecutive sunt adiacente.

În figura alăturată, segmentele S2S_2 și S5S_5 sunt conectate, deoarece există o succesiune de segmente consecutiv adiacente, și anume S2S_2, S3S_3 și S5S_5.

O submulțime de segmente formează o rețea, dacă segmentele respective sunt conectate între ele, fără a avea conexiuni cu celelalte segmente care nu aparțin submulțimii. O mulțime de segmente poate avea una sau mai multe rețele. Pentru figura de mai sus, rețelele sunt {S1,S2,S3,S5}\{S_1, S_2, S_3, S_5\}, {S4}\{S_4\} și {S6,S7}\{S_6, S_7\}.

Cerință

Cunoscând numărul de segmente și coordonatele lor, afișați numărul de rețele.

Date de intrare

Fișierul segmente.in conține pe prima linie un număr natural nn, reprezentând numărul de segmente. Pe fiecare din următoarele nn linii se găsesc coordonatele capetelor segmentului, sub forma x1x_1, y1y_1, x2x_2, y2y_2. Valorile sunt separate printr-un spațiu și sunt numere întregi.

Date de ieșire

În fişierul segmente.out fişierul segmente.out se va afişa, pe prima linie, un număr natural ce reprezintă numărul de rețele.

Restricții și precizări

  • 1n700 0001 ≤ n ≤ 700 \ 000
  • 100 000x1,y1,x2,y2100 000-100 \ 000 \leq x_1, y_1, x_2, y_2 \leq 100 \ 000

Exemplu

segmente.in

7
1 7 4 8 
2 6 4 8 
4 8 7 4 
2 4 9 7 
5 2 7 4 
8 3 11 8 
8 3 13 1 

segmente.out

3

Explicație

Exemplul din figură.

Log in or sign up to be able to send submissions!