선 그리기
시간 제한2초메모리 제한128 MB
최대 1만 개의 선분이 주어질 때, 서로 닿거나 겹치거나 교차하는 선분들을 같은 그룹으로 묶어 연결된 그룹의 수를 구하는 문제입니다.
문제
정문이는 2차원 평면에 주어진 N개의 선분을 그리려고 한다. 서로 닿아 있거나 겹치거나 교차하는 선분들은 연속해서 이어진 하나의 선 묶음으로 생각할 수 있다. 또한 어떤 선분이 다른 선분들과 차례로 이어져 있다면 모두 같은 묶음에 속한다.
N개의 선분 정보가 주어졌을 때, 전체 선분을 몇 개의 서로 분리된 선 묶음으로 나타낼 수 있는지 구하라.
입력
첫째 줄에 선분의 개수 N (1 <= N <= 10,000)이 주어진다.
둘째 줄부터 N개의 줄에는 네 수 x1, y1, x2, y2가 주어진다. 이는 (x1, y1)에서 (x2, y2)까지 이어지는 선분을 뜻한다. 모든 좌표는 0 이상 1000 이하이며, 최대 소수 둘째 자리까지 주어진다. 각 선분의 길이는 0보다 크다.
출력
서로 분리된 선 묶음의 개수를 출력한다.