시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 46 10 9 26.471%

문제

평면 상에 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+XHJcblxyXG48cD5cdWM1ZWNcdWFlMzBcdWMxMWMgM1x1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NDQgXHVhY2U4XHViNzdjIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YzU0OFx1YzVkMCBcdWIyZTRcdWI5NzggXHVjODEwXHViNGU0XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDBcdWJhNzQgXHVjNzc0XHViOTdjIFx1YzI4OFx1ZDM3YyBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NzRcdWI3N2NcdWFjZTAgXHViZDgwXHViOTc4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjYzBcdWM3NzRcdWIwOTggXHVhZjJkXHVjOWQzXHVjODEwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWI0ZTRcdWIzYzQgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YjBiNFx1YmQ4MFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzNjXHViODVjIFx1YWMwNFx1YzhmY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1YzgxMFx1YjRlNFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjMjg4XHVkMzdjIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWQ2MTVcdWMxMzFcdWQ1NThcdWIyOTQgXHVjMTM4IFx1YzgxMFx1Yzc0NCBcdWNjM2VcdWM3M2NcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOKDMgJmxlOyBOICZsZTsgMzAwKVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LjxcL3A+XHJcblxyXG48cD4oXHViMmU4LCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNzg1XHViODI1XHVjNWQwXHViMjk0IFx1ZDNjOVx1ZDU4OVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NzQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1YyBcdWMzMGRcdWM3NDAgXHVjNzg4XHViMmU0Lik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyODhcdWQzN2MgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YzU0OFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzI4OFx1ZDM3YyBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YzEzOCBcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YzU0NFx1YmIzNFx1YjgwN1x1YWM4Y1x1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTc5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoidHJva3V0IiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBhcmUgTiBkaWZmZXJlbnQgcG9pbnRzIGluIGEgcGxhbmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIHNheSB0aGF0IHRoZSB0cmlhbmdsZSBmb3JtZWQgYnkgc29tZSB0aHJlZSBwb2ludHMgYXMgY29ybmVycyBpcyBhIHN1cGVyLXRyaWFuZ2xlIGlmIHRoZSBudW1iZXIgb2YgcG9pbnRzIGluc2lkZSB0aGlzIHRyaWFuZ2xlIGlzIGFzIGxhcmdlIGFzIHBvc3NpYmxlLiBXZSBjb25zaWRlciB0aGUgcG9pbnRzIGluIHRoZSBjb3JuZXJzIG9yIG9uIHRoZSBzaWRlcyBvZiB0aGUgdHJpYW5nbGUgYXMgYmVpbmcgaW5zaWRlIHRoZSB0cmlhbmdsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCwgYW1vbmcgZ2l2ZW4gcG9pbnRzLCBmaW5kIHRocmVlIHBvaW50cyB0aGF0IGZvcm0gc29tZSBzdXBlci10cmlhbmdsZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgTiwgMyAmbGU7IE4gJmxlOyAzMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAmbmRhc2g7IHRoZSBjb29yZGluYXRlcyBvZiBvbmUgcG9pbnQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IHRoZSB0ZXN0IGRhdGEgd2lsbCBiZSBzdWNoIHRoYXQgdGhlcmUgd2lsbCBiZSBhdCBsZWFzdCB0aHJlZSBub24tY29sbGluZWFyIHBvaW50cy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIG51bWJlciBvZiBwb2ludHMgaW5zaWRlIHRoZSBzdXBlci10cmlhbmdsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIHNob3VsZCBjb250YWluIHRocmVlIG51bWJlcnMgJm5kYXNoOyBpbmRpY2VzIG9mIHRoZSB0aHJlZSBjb3JuZXIgcG9pbnRzIG9mIHRoZSBzdXBlci10cmlhbmdsZSwgaW4gYW55IG9yZGVyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d