14164번 - 삼각형 영역 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 282 | 120 | 95 | 40.598% |
문제
농부 존은 현금을 마련하기 위해 자신의 땅을 팔려고 한다. 그는 2차원 좌표평면에서 점으로 나타낼 수 있는 나무 N(3 ≤ N ≤ 300)개가 있는데, 세 점이 일직선 상에 있지 않는 꼴로 나무가 배치되어 있다. 농부 존은 서로 다른 세 나무를 꼭짓점으로 하는 삼각형 영역을 후보 삼아 파는 것을 고려하려고 한다. 즉, 총 \({N}\choose{3}\)개의 후보가 존재한다.
삼각형 영역은 세 꼭짓점을 제외한 영역 안에 존재하는 나무의 개수 v에 따라 값이 매겨진다. 세 점이 일직선 상 위에 존재하지 않으므로, 삼각형 영역의 선분 위에 나무가 존재하는 경우가 없음이 자명하다. 0이상 N-3이하의 모든 v에 대해 나무의 개수가 v인 삼각형 영역의 개수를 구하는 프로그램을 작성하시오.
입력
첫 줄에 나무의 개수를 나타내는 자연수 N이 주어진다.
그 다음 N개의 줄에 각 나무의 x, y좌표를 나타내는 두 정수가 공백으로 구분되어 주어진다. 주어지는 좌표값은 0이상 1,000,000이하다.
출력
N-2개의 줄에 걸쳐, i번째 줄에는 v=i-1인 삼각형 영역의 수를 출력한다.
예제 입력 1
7 3 6 17 15 13 15 6 12 9 1 2 7 10 19
예제 출력 1
28 6 1 0 0
출처
Olympiad > USA Computing Olympiad > 2016-2017 Season > USACO 2016 December Contest > Platinum 1번
- 문제를 번역한 사람: myungwoo
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호