점점 늘어나는 (A,B) 순서쌍 집합에서, 새 순서쌍이 기존 두 점을 잇는 선분 위에 있거나 그 선분 아래에 있는지 매일 판정한다.
어려움8기하이분 탐색정렬그리디아직 제출이 없습니다시간 제한1초메모리 제한512 MB과학자 태영이는 자기 실험실에서 이상한 용액으로 실험을 한다. 실험실에는 1L짜리 이상한 용액이 N개 있고, 각 용액에는 성분 A와 성분 B가 녹아 있다. 이 용액의 집합을 S라 하자.
어느 날 태영이는 실험에 쓸 1L 용액을 새로 만들려고 한다. 그런데 손이 많이 가는 일은 하기 싫어서 다음 두 방법만 쓴다.
용액 안에서 두 성분은 고르게 섞여 있다. 예를 들어 성분 A가 5만큼 들어 있는 1L 용액에서 0.3L를 덜어내면, 그 안에는 성분 A가 정확히 1.5만큼 들어 있다.
태영이의 이론에 따르면 성분 A와 성분 B는 많을수록 실험에 유리하다. 다만 둘 중 무엇이 많아야 더 좋은지는 모른다. 그래서 태영이는 다음 조건을 만족하는 1L 용액 K를 나쁜 용액이라고 부르기로 했다.
조건: S의 용액으로 위 두 방법 중 하나를 써서, 성분 A와 성분 B가 모두 K 이상인 용액을 만들 수 있다.
실험을 준비하던 태영이는 실험실의 용액이 너무 적다고 생각해서 용액을 새로 사기로 했다. 태영이는 M일 동안 용액을 사러 다니는데, 이것도 귀찮아서 하루에 최대 한 개만 산다. i번째 날에 하는 행동은 다음과 같다.
i번째 날의 판정은 그 전날까지 산 용액이 모두 S에 들어간 상태를 기준으로 한다.
용액을 볼 때마다 나쁜 용액인지 일일이 확인하는 일이 귀찮아진 태영이가 당신에게 도움을 청했다. 날마다 용액을 사야 하는지 판정하자.
첫째 줄에 처음에 실험실에 있던 용액의 수 N (1≤N≤105)이 주어진다.
다음 N개 줄 중 i번째 줄에는 i번째 용액에 들어 있는 성분 A의 양과 성분 B의 양을 나타내는 정수 ai, bi (0≤ai,bi≤109)가 주어진다.
다음 줄에는 태영이가 용액을 사러 다니는 날 수 M (1≤M≤105)이 주어진다.
다음 M개 줄 중 i번째 줄에는 용액 Ki에 들어 있는 성분 A의 양과 성분 B의 양을 나타내는 정수 ci, di (0≤ci,di≤109)가 주어진다.
정확히 M개의 줄을 출력한다. i번째 줄에는 태영이가 i번째 용액을 사야 하면 Yes를, 사지 말아야 하면 No를 출력한다.