시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 46 19 19 42.222%

문제

농부 존은 현금을 마련하기 위해 자신의 땅을 팔려고 한다. 그는 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
W3sicHJvYmxlbV9pZCI6IjE0MTY0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGJjXHVhYzAxXHVkNjE1IFx1YzYwMVx1YzVlZCIsImRlc2NyaXB0aW9uIjoiPHA+XHViMThkXHViZDgwIFx1Yzg3NFx1Yzc0MCBcdWQ2MDRcdWFlMDhcdWM3NDQgXHViOWM4XHViODI4XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM3OTBcdWMyZTBcdWM3NTggXHViNTQ1XHVjNzQ0IFx1ZDMxNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjI5NCAyXHVjYzI4XHVjNmQwIFx1Yzg4Y1x1ZDQ1Y1x1ZDNjOVx1YmE3NFx1YzVkMFx1YzExYyBcdWM4MTBcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMDk4XHViYjM0IE4oMyAmbGU7IE4gJmxlOyAzMDApXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjMTM4IFx1YzgxMFx1Yzc3NCBcdWM3N2NcdWM5YzFcdWMxMjAgXHVjMGMxXHVjNWQwIFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhZjM0XHViODVjIFx1YjA5OFx1YmIzNFx1YWMwMCBcdWJjMzBcdWNlNThcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWIxOGRcdWJkODAgXHVjODc0XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMTM4IFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3M2NcdWI4NWMgXHVkNTU4XHViMjk0IFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWM2MDFcdWM1ZWRcdWM3NDQgXHVkNmM0XHViY2Y0IFx1YzBiY1x1YzU0NCBcdWQzMGNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWNlMFx1YjgyNFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHVjZDFkIFxcKHtOfVxcY2hvb3NlezN9XFwpXHVhYzFjXHVjNzU4IFx1ZDZjNFx1YmNmNFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBiY1x1YWMwMVx1ZDYxNSBcdWM2MDFcdWM1ZWRcdWM3NDAgXHVjMTM4IFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc0NCBcdWM4MWNcdWM2NzhcdWQ1NWMgXHVjNjAxXHVjNWVkIFx1YzU0OFx1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHViMDk4XHViYjM0XHVjNzU4IFx1YWMxY1x1YzIxOCB2XHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWFjMTJcdWM3NzQgXHViOWU0XHVhY2E4XHVjOWM0XHViMmU0LiBcdWMxMzggXHVjODEwXHVjNzc0IFx1Yzc3Y1x1YzljMVx1YzEyMCBcdWMwYzEgXHVjNzA0XHVjNWQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJiYzBcdWI4NWMsIFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWM2MDFcdWM1ZWRcdWM3NTggXHVjMTIwXHViZDg0IFx1YzcwNFx1YzVkMCBcdWIwOThcdWJiMzRcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM1YzZcdWM3NGNcdWM3NzQgXHVjNzkwXHViYTg1XHVkNTU4XHViMmU0LiAwXHVjNzc0XHVjMGMxIE4tM1x1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWJhYThcdWI0ZTAgdlx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViMDk4XHViYjM0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCB2XHVjNzc4IFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWM2MDFcdWM1ZWRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWIwOThcdWJiMzRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YjA5OFx1YmIzNFx1Yzc1OCB4LCB5XHVjODhjXHVkNDVjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjODhjXHVkNDVjXHVhYzEyXHVjNzQwIDBcdWM3NzRcdWMwYzEgMSwwMDAsMDAwXHVjNzc0XHVkNTU4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk4tMlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwLCBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCB2PWktMVx1Yzc3OCBcdWMwYmNcdWFjMDFcdWQ2MTUgXHVjNjAxXHVjNWVkXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTQxNjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMb3RzIG9mIFRyaWFuZ2xlcyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaXMgdGhpbmtpbmcgb2Ygc2VsbGluZyBzb21lIG9mIGhpcyBsYW5kIHRvIGVhcm4gYSBiaXQgb2YgZXh0cmEgaW5jb21lLiBIaXMgcHJvcGVydHkgY29udGFpbnMgbiB0cmVlcyAoMyZsZTtOJmxlOzMwMCksIGVhY2ggZGVzY3JpYmVkIGJ5IGEgcG9pbnQgaW4gdGhlIDJEIHBsYW5lLCBubyB0aHJlZSBvZiB3aGljaCBhcmUgY29sbGluZWFyLiBGSiBpcyB0aGlua2luZyBhYm91dCBzZWxsaW5nIHRyaWFuZ3VsYXIgbG90cyBvZiBsYW5kIGRlZmluZWQgYnkgaGF2aW5nIHRyZWVzIGF0IHRoZWlyIHZlcnRpY2VzOyB0aGVyZSBhcmUgb2YgY291cnNlIEw9XFwoTiBcXGNob29zZSAzXFwpJm5ic3A7c3VjaCBsb3RzIGhlIGNhbiBjb25zaWRlciwgYmFzZWQgb24gYWxsIHBvc3NpYmxlIHRyaXBsZXMgb2YgdHJlZXMgb24gaGlzIHByb3BlcnR5LjxcL3A+XHJcblxyXG48cD5BIHRyaWFuZ3VsYXIgbG90IGhhcyB2YWx1ZSB2IGlmIGl0IGNvbnRhaW5zIGV4YWN0bHkgdiB0cmVlcyBpbiBpdHMgaW50ZXJpb3IgKHRoZSB0cmVlcyBvbiB0aGUgY29ybmVycyBkbyBub3QgY291bnQsIGFuZCBub3RlIHRoYXQgdGhlcmUgYXJlIG5vIHRyZWVzIG9uIHRoZSBib3VuZGFyaWVzIHNpbmNlIG5vIHRocmVlIHRyZWVzIGFyZSBjb2xsaW5lYXIpLiBGb3IgZXZlcnkgdj0wJmhlbGxpcDtOJm1pbnVzOzMsIHBsZWFzZSBoZWxwIEZKIGRldGVybWluZSBob3cgbWFueSBvZiBoaXMgTCBwb3RlbnRpYWwgbG90cyBoYXZlIHZhbHVlIHYuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBOLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbiB0aGUgeCBhbmQgeSBjb29yZGluYXRlcyBvZiBhIHNpbmdsZSB0cmVlOyB0aGVzZSBhcmUgYm90aCBpbnRlZ2VycyBpbiB0aGUgcmFuZ2UgMCZoZWxsaXA7MSwwMDAsMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBOJm1pbnVzOzIgbGluZXMsIHdoZXJlIG91dHB1dCBsaW5lIGkmbmJzcDtjb250YWlucyBhIGNvdW50IG9mIHRoZSBudW1iZXIgb2YgbG90cyBoYXZpbmcgdmFsdWUgaSZtaW51czsxLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==