시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 24 6 6 30.000%

문제

양의 정수를 좌표로 갖는 점 K개와, 한 점은 원점, 다른 두 점은 음이 아닌 정수를 좌표로 갖는점으로 이루어진 M개의 삼각형이 주어진다.

이 때, 각각의 삼각형의 내부에 주어진 K개의 점 중 적어도 하나는 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 K와 M이 주어진다. 둘째 줄부터 K개의 줄에는 각 점의 x좌표와 y좌표가 공백으로 구분되어 주어진다. 다음 M개의 줄에는 삼각형의 원점이 아닌 꼭지점의 좌표가 (x1, y1), (x2, y2)가 순서대로 공백으로 구분되어져서 주어진다.

1 ≤ K, M ≤ 100,000

1 ≤ K개 점의 좌표 ≤ 109

0 ≤ 삼각형 꼭지점 좌표 ≤ 109

삼각형의 넓이는 0이 아니다.

출력

M개의 줄을 출력한다. i번줄에는 i번째 입력으로 주어진 삼각형의 내부에 점이 적어도 1개 있으면 Y를, 아니면 N을 출력한다.

예제 입력 1

4 3
1 2
1 3
5 1
5 3
1 4 3 3
2 2 4 1
4 4 6 3

예제 출력 1

Y
N
Y

힌트

W3sicHJvYmxlbV9pZCI6IjMzMjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYmNcdWFjMDFcdWQ2MTUiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI5N2MgXHVjODhjXHVkNDVjXHViODVjIFx1YWMxNlx1YjI5NCBcdWM4MTAgS1x1YWMxY1x1YzY0MCwgXHVkNTVjIFx1YzgxMFx1Yzc0MCBcdWM2ZDBcdWM4MTAsIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHVjODEwXHVjNzQwIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHViOTdjIFx1Yzg4Y1x1ZDQ1Y1x1Yjg1YyBcdWFjMTZcdWIyOTRcdWM4MTBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IE1cdWFjMWNcdWM3NTggXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0IFx1YjU0YywgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIwYjRcdWJkODBcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWM0IEtcdWFjMWNcdWM3NTggXHVjODEwIFx1YzkxMSBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4XHViMjk0IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1YzZcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEtcdWM2NDAgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgS1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzgxMFx1Yzc1OCB4XHVjODhjXHVkNDVjXHVjNjQwIHlcdWM4OGNcdWQ0NWNcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjNmQwXHVjODEwXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwICh4MSwgeTEpLCAoeDIsIHkyKVx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDEgJmxlOyBLLCBNICZsZTsgMTAwLDAwMDxcL3A+XHJcbjxwPlxyXG5cdDEgJmxlOyBLXHVhYzFjIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWMgJmxlOyAxMDxzdXA+OTxcL3N1cD48XC9wPlxyXG48cD5cclxuXHQwICZsZTsgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YWYyZFx1YzljMFx1YzgxMCBcdWM4OGNcdWQ0NWMgJmxlOyAxMDxzdXA+OTxcL3N1cD48XC9wPlxyXG48cD5cclxuXHRcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMTEzXHVjNzc0XHViMjk0IDBcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gaVx1YmM4OFx1YzkwNFx1YzVkMFx1YjI5NCBpXHViYzg4XHVjOWY4IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YjBiNFx1YmQ4MFx1YzVkMCBcdWM4MTBcdWM3NzQgXHVjODAxXHVjNWI0XHViM2M0IDFcdWFjMWMgXHVjNzg4XHVjNzNjXHViYTc0IFlcdWI5N2MsIFx1YzU0NFx1YjJjOFx1YmE3NCBOXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90cmlhbmdsZWFuZHBvaW50LnBuZ1wiIHN0eWxlPVwid2lkdGg6IDMwNHB4OyBoZWlnaHQ6IDIwN3B4O1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzMyMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyaSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBLIHBvaW50cyB3aXRoIHBvc2l0aXZlIGludGVnZXIgY29vcmRpbmF0ZXMuIFlvdSBhcmUgYWxzbyBnaXZlbiBNIHRyaWFuZ2xlcywgZWFjaCBvZiB0aGVtIGhhdmluZyBvbmUgdmVydGV4IGluIHRoZSBvcmlnaW4gYW5kIHRoZSBvdGhlciAyIHZlcnRpY2VzIHdpdGggbm9uLW5lZ2F0aXZlIGludGVnZXIgY29vcmRpbmF0ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBhcmUgYXNrZWQgdG8gZGV0ZXJtaW5lIGZvciBlYWNoIHRyaWFuZ2xlIHdoZXRoZXIgaXQgaGFzIGF0IGxlYXN0IG9uZSBvZiB0aGUgSyBnaXZlbiBwb2ludHMgaW5zaWRlLiAoTm9uZSBvZiB0aGUgSyBwb2ludHMgYXJlIG9uIGFueSBlZGdlIG9mIGFueSB0cmlhbmdsZS4pPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQmbmJzcDt3aWxsIGNvbnRhaW4gSyBhbmQgTS4gVGhlIGZvbGxvd2luZyBLIGxpbmVzIHdpbGwgY29udGFpbiAyIHBvc2l0aXZlIGludGVnZXJzIHggeSBzZXBhcmF0ZWQgYnkgb25lIHNwYWNlIHRoYXQgcmVwcmVzZW50IHRoZSBjb29yZGluYXRlcyBvZiBlYWNoIHBvaW50LiBUaGUgbmV4dCBNIGxpbmVzIGhhdmUgNCBub24tbmVnYXRpdmUgaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IG9uZSBzcGFjZSwgKHgxLHkxKSBhbmQgKHgyLCB5MiksIHRoYXQgcmVwcmVzZW50IHRoZSBvdGhlciAyIHZlcnRpY2VzIG9mIGVhY2ggdHJpYW5nbGUsIGV4Y2VwdCB0aGUgb3JpZ2luLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgJmxlOyBLLE0gJmxlOyAxMDAgMDAwJm5ic3A7PFwvbGk+XHJcblx0PGxpPjEgJmxlOyBlYWNoIGNvb3JkaW5hdGUgb2YgdGhlIEsgcG9pbnRzICZsZTsgMTA8c3VwPjk8XC9zdXA+PFwvbGk+XHJcblx0PGxpPjAgJmxlOyBlYWNoIGNvb3JkaW5hdGUgb2YgdGhlIHRyaWFuZ2xlIHZlcnRpY2VzICZsZTsgMTA8c3VwPjk8XC9zdXA+PFwvbGk+XHJcblx0PGxpPlRyaWFuZ2xlcyBhcmUgbm90IGRlZ2VuZXJhdGUgKHRoZXkgYWxsIGhhdmUgbm9uemVybyBhcmVhKS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gZXhhY3RseSBNIGxpbmVzLiBUaGUgay10aCBsaW5lIHNob3VsZCBjb250YWluIHRoZSBjaGFyYWN0ZXIgWSBpZiB0aGUgay10aCB0cmlhbmdsZSAoaW4gdGhlIG9yZGVyIG9mIHRoZSBpbnB1dCBmaWxlKSBjb250YWlucyBhdCBsZWFzdCBvbmUgcG9pbnQgaW5zaWRlIGl0LCBvciBOIG90aGVyd2lzZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90cmlhbmdsZWFuZHBvaW50LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwN3B4OyB3aWR0aDozMDRweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Central European Olympiad in Informatics > CEOI 2009 6번

  • 문제의 오타를 찾은 사람: august14
  • 문제를 번역한 사람: baekjoon