시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 41 9 8 26.667%

문제

평면 상에 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
W3sicHJvYmxlbV9pZCI6IjMxNzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYmNcdWFjMDFcdWQ2MTUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDNjOVx1YmE3NCBcdWMwYzFcdWM1ZDAgTlx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZWNcdWFlMzBcdWMxMWMgM1x1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NDQgXHVhY2U4XHViNzdjIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YzU0OFx1YzVkMCBcdWIyZTRcdWI5NzggXHVjODEwXHViNGU0XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDBcdWJhNzQgXHVjNzc0XHViOTdjIFx1YzI4OFx1ZDM3YyBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NzRcdWI3N2NcdWFjZTAgXHViZDgwXHViOTc4XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHViY2MwXHVjNzc0XHViMDk4IFx1YWYyZFx1YzlkM1x1YzgxMFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjODEwXHViNGU0XHViM2M0IFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWIwYjRcdWJkODBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWM4M1x1YzczY1x1Yjg1YyBcdWFjMDRcdWM4ZmNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljNCBcdWM4MTBcdWI0ZTRcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YzI4OFx1ZDM3YyBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVkNjE1XHVjMTMxXHVkNTU4XHViMjk0IFx1YzEzOCBcdWM4MTBcdWM3NDQgXHVjYzNlXHVjNzNjXHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTigzICZsZTsgTiAmbGU7IDMwMClcdWM3NzQgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWMgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+KFx1YjJlOCwgXHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzc4NVx1YjgyNVx1YzVkMFx1YjI5NCBcdWQzYzlcdWQ1ODlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzEzOCBcdWFjMWNcdWM3NTggXHVjODEwXHVjNzc0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHVjMzBkXHVjNzQwIFx1Yzc4OFx1YjJlNC4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjg4XHVkMzdjIFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWM1NDhcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViMjk0IFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyODhcdWQzN2MgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWMxMzggXHVjODEwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWM1NDRcdWJiMzRcdWI4MDdcdWFjOGNcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxNzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJ0cm9rdXQiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBOIGRpZmZlcmVudCBwb2ludHMgaW4gYSBwbGFuZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2Ugc2F5IHRoYXQgdGhlIHRyaWFuZ2xlIGZvcm1lZCBieSBzb21lIHRocmVlIHBvaW50cyBhcyBjb3JuZXJzIGlzIGEgc3VwZXItdHJpYW5nbGUgaWYgdGhlIG51bWJlciBvZiBwb2ludHMgaW5zaWRlIHRoaXMgdHJpYW5nbGUgaXMgYXMgbGFyZ2UgYXMgcG9zc2libGUuIFdlIGNvbnNpZGVyIHRoZSBwb2ludHMgaW4gdGhlIGNvcm5lcnMgb3Igb24gdGhlIHNpZGVzIG9mIHRoZSB0cmlhbmdsZSBhcyBiZWluZyBpbnNpZGUgdGhlIHRyaWFuZ2xlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsLCBhbW9uZyBnaXZlbiBwb2ludHMsIGZpbmQgdGhyZWUgcG9pbnRzIHRoYXQgZm9ybSBzb21lIHN1cGVyLXRyaWFuZ2xlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBOLCAzICZsZTsgTiAmbGU7IDMwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzICZuZGFzaDsgdGhlIGNvb3JkaW5hdGVzIG9mIG9uZSBwb2ludC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogdGhlIHRlc3QgZGF0YSB3aWxsIGJlIHN1Y2ggdGhhdCB0aGVyZSB3aWxsIGJlIGF0IGxlYXN0IHRocmVlIG5vbi1jb2xsaW5lYXIgcG9pbnRzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIHBvaW50cyBpbnNpZGUgdGhlIHN1cGVyLXRyaWFuZ2xlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhyZWUgbnVtYmVycyAmbmRhc2g7IGluZGljZXMgb2YgdGhlIHRocmVlIGNvcm5lciBwb2ludHMgb2YgdGhlIHN1cGVyLXRyaWFuZ2xlLCBpbiBhbnkgb3JkZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d