시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWM1ZWNcdWFlMzBcdWMxMWMgM1x1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NDQgXHVhY2U4XHViNzdjIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YzU0OFx1YzVkMCBcdWIyZTRcdWI5NzggXHVjODEwXHViNGU0XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDBcdWJhNzQgXHVjNzc0XHViOTdjIFx1YzI4OFx1ZDM3YyBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NzRcdWI3N2NcdWFjZTAgXHViZDgwXHViOTc4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjYzBcdWM3NzRcdWIwOTggXHVhZjJkXHVjOWQzXHVjODEwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWI0ZTRcdWIzYzQgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YjBiNFx1YmQ4MFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzNjXHViODVjIFx1YWMwNFx1YzhmY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1YzgxMFx1YjRlNFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjMjg4XHVkMzdjIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWQ2MTVcdWMxMzFcdWQ1NThcdWIyOTQgXHVjMTM4IFx1YzgxMFx1Yzc0NCBcdWNjM2VcdWM3M2NcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOKDMgJmxlOyBOICZsZTsgMzAwKVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LjxcL3A+XHJcblxyXG48cD4oXHViMmU4LCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNzg1XHViODI1XHVjNWQwXHViMjk0IFx1ZDNjOVx1ZDU4OVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NzQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1YyBcdWMzMGRcdWM3NDAgXHVjNzg4XHViMmU0Lik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyODhcdWQzN2MgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YzU0OFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzI4OFx1ZDM3YyBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YzEzOCBcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YzU0NFx1YmIzNFx1YjgwN1x1YWM4Y1x1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE3OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6InRyb2t1dCIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlIE4gZGlmZmVyZW50IHBvaW50cyBpbiBhIHBsYW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XZSBzYXkgdGhhdCB0aGUgdHJpYW5nbGUgZm9ybWVkIGJ5IHNvbWUgdGhyZWUgcG9pbnRzIGFzIGNvcm5lcnMgaXMgYSBzdXBlci10cmlhbmdsZSBpZiB0aGUgbnVtYmVyIG9mIHBvaW50cyBpbnNpZGUgdGhpcyB0cmlhbmdsZSBpcyBhcyBsYXJnZSBhcyBwb3NzaWJsZS4gV2UgY29uc2lkZXIgdGhlIHBvaW50cyBpbiB0aGUgY29ybmVycyBvciBvbiB0aGUgc2lkZXMgb2YgdGhlIHRyaWFuZ2xlIGFzIGJlaW5nIGluc2lkZSB0aGUgdHJpYW5nbGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwsIGFtb25nIGdpdmVuIHBvaW50cywgZmluZCB0aHJlZSBwb2ludHMgdGhhdCBmb3JtIHNvbWUgc3VwZXItdHJpYW5nbGUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4sIDMgJmxlOyBOICZsZTsgMzAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgJm5kYXNoOyB0aGUgY29vcmRpbmF0ZXMgb2Ygb25lIHBvaW50LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiB0aGUgdGVzdCBkYXRhIHdpbGwgYmUgc3VjaCB0aGF0IHRoZXJlIHdpbGwgYmUgYXQgbGVhc3QgdGhyZWUgbm9uLWNvbGxpbmVhciBwb2ludHMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2YgcG9pbnRzIGluc2lkZSB0aGUgc3VwZXItdHJpYW5nbGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBzaG91bGQgY29udGFpbiB0aHJlZSBudW1iZXJzICZuZGFzaDsgaW5kaWNlcyBvZiB0aGUgdGhyZWUgY29ybmVyIHBvaW50cyBvZiB0aGUgc3VwZXItdHJpYW5nbGUsIGluIGFueSBvcmRlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=