다각형 찾기

시간 제한1초메모리 제한1024 MB

요약

좌표로 주어진 선분들에서 연결된 도형의 개수를 세고, 그중 시작점으로 돌아오는 오일러 경로가 있는 다각형의 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 그래프, 구현, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

2차원 평면 위의 선분 집합을 생각해 봅시다.

임의의 선분 집합 $L$ 에 대해, $P(L)$ 은 $L$ 에 속한 모든 선분의 끝점으로 이루어진 집합입니다.

두 선분이 끝점을 공유하면 연결되어 있다고 합니다.

선분 집합 $U$ 가 주어졌을 때, 기하 도형(줄여서 도형)은 다음 두 조건을 만족하는, 하나 이상의 선분으로 이루어진 집합 $S \subseteq U$ 입니다.

$P(S)$ 에 속한 임의의 두 점 $p_1$ , $p_2$ 에 대해, 연결된 선분을 따라 $p_1$ 에서 $p_2$ 로 이동할 수 있다.
$S$ 에 속한 모든 선분 $e$ 에 대해, $U$ 에서 $e$ 와 연결된 모든 선분은 $S$ 에 속한다.

다각형은 도형 $S$ 중에서, 어떤 끝점 $p$ 에서 출발하여 $p$ 에서 끝나는 경로로, $S$ 의 모든 선분을 정확히 한 번씩 사용하고 $P(S)$ 에서 $p$ 를 제외한 각 점을 정확히 한 번씩 방문하는 경로가 존재하는 도형입니다. 이때 $p$ 는 경로의 시작과 끝에서만 방문합니다.

그림 1에는 도형이 10개 있으며, 그중 $a$ , $b$ , $e$ , $f$ 가 다각형입니다. 점은 선분의 끝점입니다.

그림 1: 도형 10개, 다각형 4개

$b$ 는 자기 자신과 교차하지만, 교차점이 교차하는 선분들의 끝점은 아닙니다. 마찬가지로 $c$ 와 $d$ , $e$ 와 $f$ 는 교차하지만 서로 연결되어 있지 않습니다.

도형의 총 개수와 그중 다각형의 개수를 구하세요.

입력

입력은 파일의 끝(EOF)까지 이어지는 여러 줄로 주어집니다. 각 줄에는 다음 형식의 선분이 하나 이상 있습니다.

(x1,y1),(x2,y2);

여기서 $(x1,y1)$ 은 한쪽 끝점이고 $(x2,y2)$ 는 다른 쪽 끝점입니다. $0 \leq x1, y1, x2, y2 \leq 99$ 이며, 모든 좌표는 정수입니다.

구분 문자 (),;의 앞뒤에는 공백이 있을 수 있습니다. 한 줄은 최대 100자입니다.

선분은 최대 200개입니다. 같은 선분이 입력에 두 번 이상 나오지 않으며, 길이가 0인 선분은 없습니다.

선분에는 방향이 없으므로 선분 안에서 두 끝점의 순서는 의미가 없습니다. 입력에서 선분이 나오는 순서도 의미가 없습니다.

출력

정수 두 개를 공백으로 구분하여 한 줄에 출력합니다. 첫 번째 정수는 도형의 총 개수이고, 두 번째 정수는 다각형의 개수입니다.

첫 번째 예제의 점들은 그림 1의 도형과 대응합니다.

예제2

예제 1

입력

(84,84),(78,84);(68,60),(64,64);(20,85),(15,88);(0,0),(2,8);
(30,60),(30,66);(13,40),(18,38);(15,88),(15,95);(18,38),(8,38);
(31,7),(25,10);(30,66),(26,70);(40,14),(30,19);(5,85),(15,88);
(48,20),(56,26);(84,84),(84,82);(66,82),(70,86);(15,95),(25,90);
(70,86),(66,88);(59,23),(50,27);(15,88),(5,80);(78,84),(74,82);
(60,80),(66,82);(5,85),(5,80);(25,10),(40,14);(20,85),(25,90);
(20,60),(30,66);(13,36),(14,30);(30,60),(20,60);(64,64),(60,60);
(31,7),(30,19);(15,88),(25,90);(68,60),(76,64);(8,38),(13,40);
(5,85),(15,95);(0,0),(10,4);(10,30),(14,30);(74,82),(70,86);
(10,30),(12,43);(6,10),(10,4);(5,80),(20,85);(6,10),(2,8);
(60,80),(66,88);(84,82),(74,82);(12,43),(13,36);

예상 출력

10 4

예제 2

입력

(45,26),(88,34);(39,6),(67,8);(73,52),(92,38);(63,35),(18,61);
(34,23),(46,10);(2,75),(86,47);(26,18),(95,36);(59,78),(49,95);
(63,95),(67,80);(23,12),(33,46);(33,1),(46,10);(63,78),(2,75);
(2,33),(11,31);(99,98),(18,5);(88,34),(49,95);(25,43),(46,10);
(66,1),(2,75);(17,59),(2,33);(85,7),(85,59);(51,56),(63,95);
(1,48),(46,7);(66,49),(57,84);(59,78),(63,35);(0,49),(69,83);
(75,82),(51,56);(67,8),(92,38);(25,43),(86,47);(54,33),(12,42);
(87,12),(57,84);(37,92),(84,90);(18,61),(12,42);(66,49),(95,36);
(85,7),(73,52);(1,48),(99,98);(53,26),(11,31);(34,23),(86,47);
(22,91),(55,59);(23,12),(75,6);(66,1),(33,1);(33,46),(97,41);
(87,12),(66,49);(92,38),(8,19);(54,33),(97,41);(45,26),(7,53);
(39,6),(85,59);(63,78),(34,23);(76,9),(18,5);(67,80),(17,59);
(25,43),(66,1);(75,82),(53,26);(0,49),(18,61);(12,42),(19,3);
(33,1),(63,78);(76,9),(46,7);(8,19),(84,90);(8,19),(37,92);

예상 출력

7 2