지난 1964년에는 기록적인 대홍수가 자그레브 시가지를 강타했었다.

이때 건물이 많이 파괴되었는데 이는 물의 하중으로 인해 건물을 이루는 벽이 붕괴했기 때문이다.

이번 문제에서는 그런 도시 형태를 단순하게 모델화한 정보가 입력으로 들어온다.

여러분은 이를 토대로 어떤 벽이 홍수 후에도 붕괴 없이 존속할 것인지를 찾아야 한다.

이 모델은 좌표평면 상에서 N개의 점과 W개의 벽으로 표현된다.

벽은 그 N개의 점 중 둘을 연결한 선의 형태로 존재하는데 그 선은 중간에 다른 점을 관통하지 않으며 다른 선과 겹치거나 교차하지도 않는다.

단지 선의 끝점만이 서로 겹칠 수 있다. 또한 선은 좌표평면 상에서 수평선이나 수직선으로만 존재한다.

모델의 초기 상태는 비가 오기 전으로 모든 평면이 육지이다.

그러다 0이라는 시각에 홍수가 시작되어 벽으로 사방이 둘러싸이지 않은 모든 외곽이 물로 뒤덮인다.

그로부터 정확히 1시간 후에는 물과 육지의 양면 경계를 이루고 있던 벽이 수압을 견디지 못하고 모두 무너진다.

벽이 무너짐으로써 경계가 없어진 곳에는 이내 물이 더 깊숙이 들어오고 무너진 벽의 내부에 있던 다른 벽이 육지와 물의 경계가 된다.

이 벽도 역시 1시간이 더 지나면 무너질 것이다. 이 과정이 되풀이됨으로써 결국 무너질 벽은 다 무너지고 모든 영역에 물이 차게 된다.

다음은 지금까지 설명한 도시 모델의 한 예를 묘사한 것이다.

N개의 점의 좌표와 이들 점을 연결하는 W개의 벽에 대한 정보를 입력 받아

이 들 중 홍수 후에도 무너지지 않고 남아 있는 벽이 몇 개인지 찾는 프로그램을 작성하시오.

홍수 시뮬레이션(Flood)1 timer 1초 memory 32MB

홍수 시뮬레이션(Flood)1 1초 32MB