3051번 - 군사 기지 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 62 | 22 | 16 | 40.000% |
문제
상근이네 집 근처에는 군사 기지가 있다. 군사 기지에는 참호가 많이 있으며, 참호는 평면 위의 선분으로 모델링 할 수 있다.
매일 밤 대부분의 군인들은 잠을 자고, 군인 세 명은 밤새도록 참호를 감시한다. 두 군인이 서로 볼 수 있으려면, 그들 연결하는 선분이 모두 참호안에 있어야 하며, 다른 군인은 그 사이에 없어야 한다.
보안 상의 이유 때문에 군인은 모두 서로를 볼 수 있어야 한다. 군인을 배치할 수 있는 방법의 수는 총 몇 가지가 있을까?
입력
첫째 줄에 참호의 수 N이 주어진다. (1 ≤ N ≤ 20) 다음 N개 줄에는 참호의 정보가 네 양의 정수 X1, Y1, X2, Y2로 주어진다. 좌표는 모두 1000보다 작거나 같은 양의 정수 또는 0이다. (X1, Y1)과 (X2, Y2)는 참호의 양 끝 점이다.
참호는 겹칠 수도 있으며, 끝 점을 공유할 수도 있다.
출력
첫째 줄에 군인을 배치하는 방법의 수를 출력한다.
예제 입력 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
예제 출력 1
8
예제 입력 2
4 5 1 7 1 1 1 5 1 4 0 4 4 7 0 3 4
예제 출력 2
1
예제 입력 3
3 2 2 3 2 3 2 3 3 3 3 2 3
예제 출력 3
0
출처
Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #2 6번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호