실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
수진은 도시 공원의 일부 토지를 팔려고 합니다. 공원에는 총 N 그루의 나무가 있으며, 각 나무는 2D 평면상의 좌표로 나타낼 수 있습니다. (3≤N≤300) 이 나무들 중 어떤 세 그루의 나무도 일직선 상에 있지 않습니다. 수진은 나무 3그루를 꼭짓점으로 하는 삼각형 모양의 토지를 팔려고 합니다. 삼각형 토지의 가치는 삼각형 내부에 포함된 나무의 수로 결정됩니다. (꼭짓점의 나무는 포함되지 않습니다.)
당신의 임무는 각 삼각형 토지 조합에 대해 내부에 포함된 나무의 수를 계산하는 것입니다. 결과적으로, 가능한 모든 가치 (0에서 N−3까지)에 대해 해당 가치를 가진 삼각형 토지가 몇 개인지 계산해야 합니다.
첫 번째 입력 줄에는 N이 있습니다.
다음 N 줄에는 단일 나무의 x와 y 좌표가 있습니다. 이들은 모두 0…1,000,000 범위의 정수입니다.
출력은 N−2 줄로 구성되며, 출력 줄 i에는 가치가 i−1인 토지의 수를 나타냅니다.
7 3 6 17 15 13 15 6 12 9 1 2 7 10 19
28 6 1 0 0
출처: USACO 2016 December Contest, Platinum Problem 1. Lots of Triangles