시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 622 112 60 14.388%

문제

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+Tlx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NzQgXHVjODhjXHVkNDVjIFx1ZDNjOVx1YmE3NCBcdWMwYzFcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzkxMSBwIFx1ZDM3Y1x1YzEzY1x1ZDJiOCBcdWM3NzRcdWMwYzFcdWM3NTggXHVjODEwXHViNGU0XHVjNzQ0IFx1YzljMFx1YjA5OFx1YjI5NCBcdWM5YzFcdWMxMjBcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHVjOWMwIFx1ZDMxMFx1YmNjNFx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjOTg5LCAwLjAxTnBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzgxMFx1Yzc0NCBcdWM5YzBcdWIwOThcdWIyOTQgXHVjOWMxXHVjMTIwXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWQzMTBcdWJjYzRcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDA8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTBcdWM3NTggXHVjMjE4IG4gKDEgJmxlOyBuICZsZTsgMTA8c3VwPjU8XC9zdXA+KTxcL2xpPlxyXG5cdDxsaT5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM5YzFcdWMxMjBcdWM3NzQgXHVjOWMwXHViMDk4XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM4MTBcdWM3NTggXHVkMzdjXHVjMTNjXHVkMmYwXHVjOWMwIHAgKDIwICZsZTsgcCAmbGU7IDEwMCk8XC9saT5cclxuXHQ8bGk+XHVjNzc0XHVkNmM0IG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWMgeCwgeSAoMCAmbGU7IHgsIHkgJmxlOyAxMDxzdXA+OTxcL3N1cD4pPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjODEwXHViNGU0XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhZGY4XHViN2VjXHVkNTVjIFx1YzljMVx1YzEyMFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzQgcG9zc2libGUsIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQgaW1wb3NzaWJsZVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Yzc4NVx1YjgyNSBcdWM2MDhcdWM4MWMgMVx1YzVkMFx1YzExYyAoMCwgMCkgXC8gKDMsIDMpIFwvICgxMCwgMTApXHVjNzQ0IFx1YzljMFx1YjA5OFx1YjI5NCBcdWM5YzFcdWMxMjBcdWM3NDQgXHVjYzNlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIDIuNzVcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzgxMFx1Yzc0NCBcdWM5YzBcdWIwYWNcdWM3M2NcdWIyYzggXHVhZGY4XHViN2VjXHVkNTVjIFx1YzljMVx1YzEyMFx1Yzc3NCBcdWM3ODhcdWIyZTRcdWFjZTAgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDUyMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpbmRpbmcgTGluZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkFubmFiZWwgYW5kIFJpY2hhcmQgbGlrZSB0byBpbnZlbnQgbmV3IGdhbWVzIGFuZCBwbGF5IGFnYWluc3QgZWFjaCBvdGhlci4gT25lIGRheSBBbm5hYmVsIGhhcyBhIG5ldyBnYW1lIGZvciBSaWNoYXJkLiBJbiB0aGlzIGdhbWUgdGhlcmUgaXMgYSBnYW1lIG1hc3RlciBhbmQgYSBwbGF5ZXIuIFRoZSBnYW1lIG1hc3RlciBkcmF3cyBuIHBvaW50cyBvbiBhIHBpZWNlIG9mIHBhcGVyLiBUaGUgdGFzayBmb3IgdGhlIHBsYXllciBpcyB0byBmaW5kIGEgc3RyYWlnaHQgbGluZSwgc3VjaCB0aGF0IGF0IGxlYXN0IHAgcGVyY2VudCBvZiB0aGUgcG9pbnRzIGxpZSBleGFjdGx5IG9uIHRoYXQgbGluZS4gUmljaGFyZCBhbmQgQW5uYWJlbCBoYXZlIHZlcnkgZ29vZCB0b29scyBmb3IgbWVhc3VyZW1lbnQgYW5kIGRyYXdpbmcuIFRoZXJlZm9yZSB0aGV5IGNhbiBjaGVjayB3aGV0aGVyIGEgcG9pbnQgbGllcyBleGFjdGx5IG9uIGEgbGluZSBvciBub3QuIElmIHRoZSBwbGF5ZXIgY2FuIGZpbmQgc3VjaCBhIGxpbmUgdGhlbiB0aGUgcGxheWVyIHdpbnMuIE90aGVyd2lzZSB0aGUgZ2FtZSBtYXN0ZXIgd2lucyB0aGUgZ2FtZS48XC9wPlxyXG5cclxuPHA+VGhlcmUgaXMganVzdCBvbmUgcHJvYmxlbS4gVGhlIGdhbWUgbWFzdGVyIGNhbiBkcmF3IHRoZSBwb2ludHMgaW4gYSB3YXkgc3VjaCB0aGF0IGl0IGlzIG5vdCBwb3NzaWJsZSBhdCBhbGwgdG8gZHJhdyBhIHN1aXRhYmxlIGxpbmUuIFRoZXkgbmVlZCBhbiBpbmRlcGVuZGVudCBtZWNoYW5pc20gdG8gY2hlY2sgd2hldGhlciB0aGVyZSBldmVuIGV4aXN0cyBhIGxpbmUgY29udGFpbmluZyBhdCBsZWFzdCBwIHBlcmNlbnQgb2YgdGhlIHBvaW50cywgaS5lLiwgZG4gJm1pZGRvdDsgcFwvMTAwZSBwb2ludHMuIE5vdyBpdCBpcyB1cCB0byB5b3UgdG8gaGVscCB0aGVtIGFuZCB3cml0ZSBhIHByb2dyYW0gdG8gc29sdmUgdGhpcyB0YXNrLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggb25lIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAxMDxzdXA+NTxcL3N1cD4pLCB0aGUgbnVtYmVyIG9mIHBvaW50cyB0aGUgZ2FtZSBtYXN0ZXIgaGFzIGRyYXduOzxcL2xpPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIG9uZSBpbnRlZ2VyIHAgKDIwICZsZTsgcCAmbGU7IDEwMCksIHRoZSBwZXJjZW50YWdlIG9mIHBvaW50cyB3aGljaCBuZWVkIHRvIGxpZSBvbiB0aGUgbGluZTs8XC9saT5cclxuXHQ8bGk+biBsaW5lcyBlYWNoIHdpdGggdHdvIGludGVnZXJzIHggYW5kIHkgKDAgJmxlOyB4LCB5ICZsZTsgMTA8c3VwPjk8XC9zdXA+KSwgdGhlIGNvb3JkaW5hdGVzIG9mIGEgcG9pbnQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Tm8gdHdvIHBvaW50cyB3aWxsIGNvaW5jaWRlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIGVpdGhlciAmbGRxdW87cG9zc2libGUmcmRxdW87IGlmIGl0IGlzIHBvc3NpYmxlIHRvIGZpbmQgYSBzdWl0YWJsZSBsaW5lIG9yICZsZHF1bztpbXBvc3NpYmxlJnJkcXVvOyBvdGhlcndpc2UuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2YxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE3NnB4OyB3aWR0aDoxOTZweFwiIFwvPjxcL3A+XHJcblxyXG48cD4oYSkgU2FtcGxlIGlucHV0IDE6IEEgbGluZSB3aXRoIChhdCBsZWFzdCkgMyBvZiB0aGUgcG9pbnRzIGV4aXN0cy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvZjIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTgycHg7IHdpZHRoOjE5OXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPihiKSBTYW1wbGUgaW5wdXQgMjogTm8gbGluZSB3aXRoIGF0IGxlYXN0IDMgcG9pbnRzIGV4aXN0cy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==