시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB47111028.571%

문제

평면 상에 N개의 점이 있다.

여기서 3개의 점을 골라 삼각형을 만들었을 때, 이 삼각형 안에 다른 점들이 최대로 들어가면 이를 슈퍼 삼각형이라고 부른다. 이때, 삼각형의 변이나 꼭짓점에 있는 점들도 삼각형 내부에 있는 것으로 간주한다.

주어진 점들을 가지고 슈퍼 삼각형을 형성하는 세 점을 찾으시오.

입력

첫 번째 줄에는 N(3 ≤ N ≤ 300)이 들어온다.

다음 N개의 줄에는 각 점의 좌표 xi, yi가 들어온다.

단, 주어진 입력에는 평행하지 않은 세 개의 점이 적어도 한 쌍은 있다.

출력

첫 번째 줄에 슈퍼 삼각형 안에 포함되는 점의 개수를 출력한다.

두 번째 줄에 슈퍼 삼각형을 이루는 세 점의 번호를 아무렇게나 출력한다.

예제 입력 1

6
1 3
2 3
2 1
3 1
3 2
4 4

예제 출력 1

5
1 4 6

예제 입력 2

9
1 1
2 2
3 3
2 1
3 2
3 1
4 2
4 1
5 1

예제 출력 2

9
1 9 3

예제 입력 3

13
1 3
2 4
3 1
4 1
4 2
4 3
4 4
4 5
5 1
5 2
6 1
6 5
7 3

예제 출력 3

9
3 11 8
W3sicHJvYmxlbV9pZCI6IjMxNzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYmNcdWFjMDFcdWQ2MTUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDNjOVx1YmE3NCBcdWMwYzFcdWM1ZDAgTlx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZWNcdWFlMzBcdWMxMWMgM1x1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NDQgXHVhY2U4XHViNzdjIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YzU0OFx1YzVkMCBcdWIyZTRcdWI5NzggXHVjODEwXHViNGU0XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDBcdWJhNzQgXHVjNzc0XHViOTdjIFx1YzI4OFx1ZDM3YyBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NzRcdWI3N2NcdWFjZTAgXHViZDgwXHViOTc4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjYzBcdWM3NzRcdWIwOTggXHVhZjJkXHVjOWQzXHVjODEwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWI0ZTRcdWIzYzQgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YjBiNFx1YmQ4MFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzNjXHViODVjIFx1YWMwNFx1YzhmY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1YzgxMFx1YjRlNFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjMjg4XHVkMzdjIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWQ2MTVcdWMxMzFcdWQ1NThcdWIyOTQgXHVjMTM4IFx1YzgxMFx1Yzc0NCBcdWNjM2VcdWM3M2NcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOKDMgJmxlOyBOICZsZTsgMzAwKVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTgsIFx1YzhmY1x1YzViNFx1YzljNCBcdWM3ODVcdWI4MjVcdWM1ZDBcdWIyOTQgXHVkM2M5XHVkNTg5XHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxMFx1Yzc3NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YzMwZFx1Yzc0MCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjg4XHVkMzdjIFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWM1NDhcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViMjk0IFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyODhcdWQzN2MgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWMxMzggXHVjODEwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWM1NDRcdWJiMzRcdWI4MDdcdWFjOGNcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMxNzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJ0cm9rdXQiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBOIGRpZmZlcmVudCBwb2ludHMgaW4gYSBwbGFuZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2Ugc2F5IHRoYXQgdGhlIHRyaWFuZ2xlIGZvcm1lZCBieSBzb21lIHRocmVlIHBvaW50cyBhcyBjb3JuZXJzIGlzIGEgc3VwZXItdHJpYW5nbGUgaWYgdGhlIG51bWJlciBvZiBwb2ludHMgaW5zaWRlIHRoaXMgdHJpYW5nbGUgaXMgYXMgbGFyZ2UgYXMgcG9zc2libGUuIFdlIGNvbnNpZGVyIHRoZSBwb2ludHMgaW4gdGhlIGNvcm5lcnMgb3Igb24gdGhlIHNpZGVzIG9mIHRoZSB0cmlhbmdsZSBhcyBiZWluZyBpbnNpZGUgdGhlIHRyaWFuZ2xlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsLCBhbW9uZyBnaXZlbiBwb2ludHMsIGZpbmQgdGhyZWUgcG9pbnRzIHRoYXQgZm9ybSBzb21lIHN1cGVyLXRyaWFuZ2xlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBOLCAzICZsZTsgTiAmbGU7IDMwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzICZuZGFzaDsgdGhlIGNvb3JkaW5hdGVzIG9mIG9uZSBwb2ludC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogdGhlIHRlc3QgZGF0YSB3aWxsIGJlIHN1Y2ggdGhhdCB0aGVyZSB3aWxsIGJlIGF0IGxlYXN0IHRocmVlIG5vbi1jb2xsaW5lYXIgcG9pbnRzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIHBvaW50cyBpbnNpZGUgdGhlIHN1cGVyLXRyaWFuZ2xlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhyZWUgbnVtYmVycyAmbmRhc2g7IGluZGljZXMgb2YgdGhlIHRocmVlIGNvcm5lciBwb2ludHMgb2YgdGhlIHN1cGVyLXRyaWFuZ2xlLCBpbiBhbnkgb3JkZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==