시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 602 102 56 13.625%

문제

N개의 점이 좌표 평면 상에 있을 때, 이 중 p 퍼센트 이상의 점들을 지나는 직선이 존재하는지 판별하시오. 즉, 0.01Np개 이상의 점을 지나는 직선이 존재하는지를 판별하시오.

입력

입력은

  • 첫번째 줄에 점의 수 n (1 ≤ n ≤ 105)
  • 두번째 줄에 직선이 지나야 하는 점의 퍼센티지 p (20 ≤ p ≤ 100)
  • 이후 n개의 줄에 점의 좌표 x, y (0 ≤ x, y ≤ 109)

의 형태로 주어진다. 

주어지는 모든 점들은 서로 다르다.

출력

그러한 직선이 존재하면 possible, 존재하지 않는다면 impossible을 출력한다.

예제 입력 1

5
55
0 0
10 10
10 0
0 10
3 3

예제 출력 1

possible

예제 입력 2

5
45
0 0
10 10
10 0
0 10
3 4

예제 출력 2

impossible

힌트

입력 예제 1에서 (0, 0) / (3, 3) / (10, 10)을 지나는 직선을 찾을 수 있다. 2.75개 이상의 점을 지났으니 그러한 직선이 있다고 볼 수 있다.

W3sicHJvYmxlbV9pZCI6IjEwNTIzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjOWMxXHVjMTIwIFx1Y2MzZVx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+Tlx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NzQgXHVjODhjXHVkNDVjIFx1ZDNjOVx1YmE3NCBcdWMwYzFcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzkxMSBwIFx1ZDM3Y1x1YzEzY1x1ZDJiOCBcdWM3NzRcdWMwYzFcdWM3NTggXHVjODEwXHViNGU0XHVjNzQ0IFx1YzljMFx1YjA5OFx1YjI5NCBcdWM5YzFcdWMxMjBcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHVjOWMwIFx1ZDMxMFx1YmNjNFx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjOTg5LCAwLjAxTnBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzgxMFx1Yzc0NCBcdWM5YzBcdWIwOThcdWIyOTQgXHVjOWMxXHVjMTIwXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWQzMTBcdWJjYzRcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDA8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxMFx1Yzc1OCBcdWMyMTggbiAoMSAmbGU7IG4gJmxlOyAxMDxzdXA+NTxcL3N1cD4pPFwvbGk+XHJcblx0PGxpPlx1YjQ1MFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWMxXHVjMTIwXHVjNzc0IFx1YzljMFx1YjA5OFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjODEwXHVjNzU4IFx1ZDM3Y1x1YzEzY1x1ZDJmMFx1YzljMCBwICgyMCAmbGU7IHAgJmxlOyAxMDApPFwvbGk+XHJcblx0PGxpPlx1Yzc3NFx1ZDZjNCBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjIHgsIHkgKDAgJmxlOyB4LCB5ICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzc1OCBcdWQ2MTVcdWQwZGNcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViYWE4XHViNGUwIFx1YzgxMFx1YjRlNFx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWRmOFx1YjdlY1x1ZDU1YyBcdWM5YzFcdWMxMjBcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViYTc0IHBvc3NpYmxlLCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0IGltcG9zc2libGVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM3ODVcdWI4MjUgXHVjNjA4XHVjODFjIDFcdWM1ZDBcdWMxMWMgKDAsIDApIFwvICgzLCAzKSBcLyAoMTAsIDEwKVx1Yzc0NCBcdWM5YzBcdWIwOThcdWIyOTQgXHVjOWMxXHVjMTIwXHVjNzQ0IFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiAyLjc1XHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWM4MTBcdWM3NDQgXHVjOWMwXHViMGFjXHVjNzNjXHViMmM4IFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWM5YzFcdWMxMjBcdWM3NzQgXHVjNzg4XHViMmU0XHVhY2UwIFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA1MjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGaW5kaW5nIExpbmVzIiwiZGVzY3JpcHRpb24iOiI8cD5Bbm5hYmVsIGFuZCBSaWNoYXJkIGxpa2UgdG8gaW52ZW50IG5ldyBnYW1lcyBhbmQgcGxheSBhZ2FpbnN0IGVhY2ggb3RoZXIuIE9uZSBkYXkgQW5uYWJlbCBoYXMgYSBuZXcgZ2FtZSBmb3IgUmljaGFyZC4gSW4gdGhpcyBnYW1lIHRoZXJlIGlzIGEgZ2FtZSBtYXN0ZXIgYW5kIGEgcGxheWVyLiBUaGUgZ2FtZSBtYXN0ZXIgZHJhd3MgbiBwb2ludHMgb24gYSBwaWVjZSBvZiBwYXBlci4gVGhlIHRhc2sgZm9yIHRoZSBwbGF5ZXIgaXMgdG8gZmluZCBhIHN0cmFpZ2h0IGxpbmUsIHN1Y2ggdGhhdCBhdCBsZWFzdCBwIHBlcmNlbnQgb2YgdGhlIHBvaW50cyBsaWUgZXhhY3RseSBvbiB0aGF0IGxpbmUuIFJpY2hhcmQgYW5kIEFubmFiZWwgaGF2ZSB2ZXJ5IGdvb2QgdG9vbHMgZm9yIG1lYXN1cmVtZW50IGFuZCBkcmF3aW5nLiBUaGVyZWZvcmUgdGhleSBjYW4gY2hlY2sgd2hldGhlciBhIHBvaW50IGxpZXMgZXhhY3RseSBvbiBhIGxpbmUgb3Igbm90LiBJZiB0aGUgcGxheWVyIGNhbiBmaW5kIHN1Y2ggYSBsaW5lIHRoZW4gdGhlIHBsYXllciB3aW5zLiBPdGhlcndpc2UgdGhlIGdhbWUgbWFzdGVyIHdpbnMgdGhlIGdhbWUuPFwvcD5cclxuXHJcbjxwPlRoZXJlIGlzIGp1c3Qgb25lIHByb2JsZW0uIFRoZSBnYW1lIG1hc3RlciBjYW4gZHJhdyB0aGUgcG9pbnRzIGluIGEgd2F5IHN1Y2ggdGhhdCBpdCBpcyBub3QgcG9zc2libGUgYXQgYWxsIHRvIGRyYXcgYSBzdWl0YWJsZSBsaW5lLiBUaGV5IG5lZWQgYW4gaW5kZXBlbmRlbnQgbWVjaGFuaXNtIHRvIGNoZWNrIHdoZXRoZXIgdGhlcmUgZXZlbiBleGlzdHMgYSBsaW5lIGNvbnRhaW5pbmcgYXQgbGVhc3QgcCBwZXJjZW50IG9mIHRoZSBwb2ludHMsIGkuZS4sIGRuICZtaWRkb3Q7IHBcLzEwMGUgcG9pbnRzLiBOb3cgaXQgaXMgdXAgdG8geW91IHRvIGhlbHAgdGhlbSBhbmQgd3JpdGUgYSBwcm9ncmFtIHRvIHNvbHZlIHRoaXMgdGFzay48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZjo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIG9uZSBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMTA8c3VwPjU8XC9zdXA+KSwgdGhlIG51bWJlciBvZiBwb2ludHMgdGhlIGdhbWUgbWFzdGVyIGhhcyBkcmF3bjs8XC9saT5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBvbmUgaW50ZWdlciBwICgyMCAmbGU7IHAgJmxlOyAxMDApLCB0aGUgcGVyY2VudGFnZSBvZiBwb2ludHMgd2hpY2ggbmVlZCB0byBsaWUgb24gdGhlIGxpbmU7PFwvbGk+XHJcblx0PGxpPm4gbGluZXMgZWFjaCB3aXRoIHR3byBpbnRlZ2VycyB4IGFuZCB5ICgwICZsZTsgeCwgeSAmbGU7IDEwPHN1cD45PFwvc3VwPiksIHRoZSBjb29yZGluYXRlcyBvZiBhIHBvaW50LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPk5vIHR3byBwb2ludHMgd2lsbCBjb2luY2lkZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyBlaXRoZXIgJmxkcXVvO3Bvc3NpYmxlJnJkcXVvOyBpZiBpdCBpcyBwb3NzaWJsZSB0byBmaW5kIGEgc3VpdGFibGUgbGluZSBvciAmbGRxdW87aW1wb3NzaWJsZSZyZHF1bzsgb3RoZXJ3aXNlLjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9mMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNzZweDsgd2lkdGg6MTk2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+KGEpIFNhbXBsZSBpbnB1dCAxOiBBIGxpbmUgd2l0aCAoYXQgbGVhc3QpIDMgb2YgdGhlIHBvaW50cyBleGlzdHMuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2YyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4MnB4OyB3aWR0aDoxOTlweFwiIFwvPjxcL3A+XHJcblxyXG48cD4oYikgU2FtcGxlIGlucHV0IDI6IE5vIGxpbmUgd2l0aCBhdCBsZWFzdCAzIHBvaW50cyBleGlzdHMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=