Informatica Online Judge

  저격 #1 [1798 / 0706]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 53   Total Tried : 71


The Champion of this Problem (C++) : gs17044 - ms / 449byte
My Best Submission (C++) : N/A

[koistudy.net (34st 박관영)]

Background

시논(Sinon)은 경기 건 온라인(GGO)에서 유명한 저격수이다. 그녀는 이번에 열리는 최대 권위의 GGO 대회 BoG(Bullets of GSHS)에 참가하였다.

경기가 시작된 지 10분 뒤, 경기의 관례에 따라 새틀라이트 스킨으로 각자의 위치가 공개되었다. 각자의 위치 좌표는 $xy$평면 위에 있으며, $x$좌표는 $0$이상 $H$이하, $y$좌표는 $0$이상 $W$ 이하이다. 그녀는 자신으로부터 플레이어들 간의 거리가 너무 멀다는 것을 깨닫고 “견제 샷”을 쏘려고 한다.

“견제 샷”이란, 불릿라인(총알의 궤도)이 플레이어들을 나눌 수 있는 샷을 말한다. 다시 말하자면, “견제 샷”이 아닌 샷은 모든 플레이어가 불릿라인 기준으로 한 쪽에 몰려있는 경우이다. 두 플레이어는 같은 위치에 있을 수 있으나, 불릿라인 위에 플레이어가 있는 경우는 없다고 보아도 좋다.(그럴 수 있다면 굳이 견제를 하지 않을 것이다)

문득, 시논은 임의의 불릿라인에 대하여 과연 이 샷이 “견제 샷”인지 궁금해졌다. 시논의 궁금증을 해결해주자.

Input

입력의 첫줄에 참가자의 명수 $N$과 불릿라인의 수 $Q$가 주어진다.($N<=100,000, Q<=100,000$)

두 번째 줄에는 대회장의 크기 $(H, W)$가 주어진다.$(1<=H<=10^9, 1<=W<=10^9)$
그 뒤 $N$개의 줄에는 참가자의 좌표가 $(x, y)$로 주어진다.$(0<=x<=H, 0<=y<=W)$
그 뒤 $Q$개의 줄에는 $ax+by+c=0$의 꼴의 불릿라인을 나타내는 $a$,$b$,$c$가 주어진다.($-10^9<=a,b,c<=10^9$)

[입력값의 정의역]
Subtask #1 : N<=1000, Q<=1000
Subtask #2 : Q<=30,000, H<=500, W<=500
Subtask #3 : N<=5000
Subtask #4 : 모든 불릿라인은 (0,0)을 지난다.
Subtask #5 : 제약 조건 없음.

Output

$Q$개의 불릿라인에 대하여, 이 샷이 “견제 샷”이면 "Yes", 아니면 "No"를 한 줄당 하나씩 출력하여라.(따옴표 제외)

IO Example

입력
5 5
100 100
0 0
2 2
0 4
4 0
4 4
1 -1 2
2 -1 2
-2 -1 2
1 0 1
0 -1 5

출력
Yes
Yes
Yes
No
No

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]