저격1 > 문제은행



문제은행

3362 : 저격1

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 1 회    시도횟수: 21 회   



시논(Sinon)은 KOI 건 온라인(KGO)에서 유명한 저격수이다. 

그녀는 이번에 열리는 최대 권위의 KGO 대회 BoK(Bullets of KOI)에 참가하였다.

 

경기가 시작된 지 10분 뒤, 경기의 관례에 따라 새틀라이트 스킨으로 각자의 위치가 공개되었다. 

각자의 위치 좌표는 xy평면 위에 있으며, x좌표는 1이상 H이하, y좌표는 1이상 W 이하이다. 

그녀는 자신으로부터 플레이어들 간의 거리가 너무 멀다는 것을 깨닫고 “견제 샷”을 쏘려고 한다.

 

“견제 샷”이란, 불릿라인(총알의 궤도)이 플레이어들을 나눌 수 있는 샷을 말한다. 

다시 말하자면, “견제 샷”이 아닌 샷은 모든 플레이어가 불릿라인 기준으로 한 쪽에 몰려있는 경우이다. 

두 플레이어는 같은 위치에 있을 수 있으나, 불릿라인 위에 플레이어가 있는 경우는 없다고 보아도 좋다.

(그럴 수 있다면 굳이 견제를 하지 않을 것이다)

 

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

시논의 궁금증을 해결해주자.

 




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



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

[부분점수 제한]
Subtask 1 : N<=1000, Q<=1000 (20점)
Subtask 2 : Q<=30000, H<=500, W<=500 (10점)
Subtask 3 : N<=5000 (15점)
Subtask 4 : 모든 불릿라인은 (0,0)을 지난다. (25점)
Subtask 5 : 제한 조건 없음(30점)


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


출처 : william202




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.