시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 28 7 7 29.167%

문제

양의 정수를 좌표로 갖는 점 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+XHJcblx0XHVjNzc0XHViNTRjLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YjBiNFx1YmQ4MFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzQgS1x1YWMxY1x1Yzc1OCBcdWM4MTAgXHVjOTExIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOThcdWIyOTQgXHVjNzg4XHViMjk0XHVjOWMwIFx1YzVjNlx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgS1x1YzY0MCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjODEwXHVjNzU4IHhcdWM4OGNcdWQ0NWNcdWM2NDAgeVx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM2ZDBcdWM4MTBcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgKHgxLCB5MSksICh4MiwgeTIpXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4XHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0MSAmbGU7IEssIE0gJmxlOyAxMDAsMDAwPFwvcD5cclxuPHA+XHJcblx0MSAmbGU7IEtcdWFjMWMgXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyAmbGU7IDEwPHN1cD45PFwvc3VwPjxcL3A+XHJcbjxwPlxyXG5cdDAgJmxlOyBcdWMwYmNcdWFjMDFcdWQ2MTUgXHVhZjJkXHVjOWQzXHVjODEwIFx1Yzg4Y1x1ZDQ1YyAmbGU7IDEwPHN1cD45PFwvc3VwPjxcL3A+XHJcbjxwPlxyXG5cdFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxMTNcdWM3NzRcdWIyOTQgMFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0TVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBpXHViYzg4XHVjOTA0XHVjNWQwXHViMjk0IGlcdWJjODhcdWM5ZjggXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMGI0XHViZDgwXHVjNWQwIFx1YzgxMFx1Yzc3NCBcdWM4MDFcdWM1YjRcdWIzYzQgMVx1YWMxYyBcdWM3ODhcdWM3M2NcdWJhNzQgWVx1Yjk3YywgXHVjNTQ0XHViMmM4XHViYTc0IE5cdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RyaWFuZ2xlYW5kcG9pbnQucG5nXCIgc3R5bGU9XCJ3aWR0aDogMzA0cHg7IGhlaWdodDogMjA3cHg7XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMzIzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJpIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGdpdmVuIEsgcG9pbnRzIHdpdGggcG9zaXRpdmUgaW50ZWdlciBjb29yZGluYXRlcy4gWW91IGFyZSBhbHNvIGdpdmVuIE0gdHJpYW5nbGVzLCBlYWNoIG9mIHRoZW0gaGF2aW5nIG9uZSB2ZXJ0ZXggaW4gdGhlIG9yaWdpbiBhbmQgdGhlIG90aGVyIDIgdmVydGljZXMgd2l0aCBub24tbmVnYXRpdmUgaW50ZWdlciBjb29yZGluYXRlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IGFyZSBhc2tlZCB0byBkZXRlcm1pbmUgZm9yIGVhY2ggdHJpYW5nbGUgd2hldGhlciBpdCBoYXMgYXQgbGVhc3Qgb25lIG9mIHRoZSBLIGdpdmVuIHBvaW50cyBpbnNpZGUuIChOb25lIG9mIHRoZSBLIHBvaW50cyBhcmUgb24gYW55IGVkZ2Ugb2YgYW55IHRyaWFuZ2xlLik8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCZuYnNwO3dpbGwgY29udGFpbiBLIGFuZCBNLiBUaGUgZm9sbG93aW5nIEsgbGluZXMgd2lsbCBjb250YWluIDIgcG9zaXRpdmUgaW50ZWdlcnMgeCB5IHNlcGFyYXRlZCBieSBvbmUgc3BhY2UgdGhhdCByZXByZXNlbnQgdGhlIGNvb3JkaW5hdGVzIG9mIGVhY2ggcG9pbnQuIFRoZSBuZXh0IE0gbGluZXMgaGF2ZSA0IG5vbi1uZWdhdGl2ZSBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgb25lIHNwYWNlLCAoeDEseTEpIGFuZCAoeDIsIHkyKSwgdGhhdCByZXByZXNlbnQgdGhlIG90aGVyIDIgdmVydGljZXMgb2YgZWFjaCB0cmlhbmdsZSwgZXhjZXB0IHRoZSBvcmlnaW4uPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7IEssTSAmbGU7IDEwMCAwMDAmbmJzcDs8XC9saT5cclxuXHQ8bGk+MSAmbGU7IGVhY2ggY29vcmRpbmF0ZSBvZiB0aGUgSyBwb2ludHMgJmxlOyAxMDxzdXA+OTxcL3N1cD48XC9saT5cclxuXHQ8bGk+MCAmbGU7IGVhY2ggY29vcmRpbmF0ZSBvZiB0aGUgdHJpYW5nbGUgdmVydGljZXMgJmxlOyAxMDxzdXA+OTxcL3N1cD48XC9saT5cclxuXHQ8bGk+VHJpYW5nbGVzIGFyZSBub3QgZGVnZW5lcmF0ZSAodGhleSBhbGwgaGF2ZSBub256ZXJvIGFyZWEpLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBzaG91bGQgY29udGFpbiBleGFjdGx5IE0gbGluZXMuIFRoZSBrLXRoIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIGNoYXJhY3RlciBZIGlmIHRoZSBrLXRoIHRyaWFuZ2xlIChpbiB0aGUgb3JkZXIgb2YgdGhlIGlucHV0IGZpbGUpIGNvbnRhaW5zIGF0IGxlYXN0IG9uZSBwb2ludCBpbnNpZGUgaXQsIG9yIE4gb3RoZXJ3aXNlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RyaWFuZ2xlYW5kcG9pbnQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjA3cHg7IHdpZHRoOjMwNHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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