레이팅 미적용설명
어느 군사 기지 근처에 참호 시스템이 있는데, 이는 평면 위의 선분들로 모델링된다. 대부분의 병사가 깊이 잠든 밤 동안, 세 명의 경비병이 참호를 지킨다. 두 경비병 사이의 직선 선분 전체를 따라 참호(또는 참호들의 연속)가 있고 그 선분 위에 세 번째 경비병이 없으면, 두 경비병은 서로를 볼 수 있다.
보안상의 이유로, 경비병들은 각 경비병이 나머지 두 명을 볼 수 있도록 배치되어야 한다. 이들을 배치하는 방법은 몇 가지인가?
제약
입력 형식
첫째 줄에 참호의 개수인 정수 \(N\) (\(1 \le N \le 100\))이 주어진다. 다음 \(N\)개의 줄에는 참호 하나의 설명이 주어진다: 네 정수 \(x_1\), \(y_1\), \(x_2\), \(y_2\) (각각 \(0\) 이상 \(100\) 이하)이며, \((x_1, y_1)\)은 한쪽 끝의 좌표, \((x_2, y_2)\)는 다른 쪽 끝의 좌표이다.
입력의 참호들은 겹치거나 끝점을 공유할 수 있다.
출력 형식
경비병을 배치하는 방법의 수를 한 줄에 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 110점 |
예제 1
입력
6
0 0 1 0
0 0 0 1
1 0 1 1
0 1 1 1
0 0 1 1
1 0 0 1출력
8예제 2
입력
4
5 1 7 1
1 1 5 1
4 0 4 4
7 0 3 4출력
1예제 3
입력
3
2 2 3 2
3 2 3 3
3 3 2 3출력
0문제 정보
태그