Knights and Dragons
시간 제한4초메모리 제한512 MB
서로 다른 n개의 점 (strength, magic)이 주어질 때, 각 점이 나머지 점들의 볼록 껍질 내부에 있는지 판별한다. 다른 점들을 반복해 가중 평균으로 만들 수 있는 점은 볼록 껍질의 꼭짓점이 아닌 점과 정확히 일치한다.
문제
Max는 Knights and Dragons를 플레이한다. 게임을 하는 동안 Max는 검을 여러 자루 모은다. 각 검에는 세 가지 속성이 있다. 힘, 마법, 그리고 판매 가능 여부(시장에서 팔 수 있는지)이다. 나중에 Max는 Sword Twister라는 주문을 얻는다. 이 주문은 검 두 자루를 가져다 새 검 한 자루를 만든다(주문을 쓴 뒤에도 원래 검 두 자루는 그대로 쓸 수 있고 속성도 변하지 않는다). 주문을 쓰려면 Max가 백분율을 하나 정하고, Sword Twister는 힘과 마법이 원래 두 검의 가중 평균인 새 검을 만든다. 정한 백분율은 0% 초과 100% 미만이어야 하며(양 끝값은 포함하지 않는다) 정수일 필요는 없다. 새로 만든 검은 팔 수 없다.
새 주문을 얻은 덕분에 쓸모없어진 검이 생겼으므로 Max는 그것을 시장에 팔 수 있다. 예를 들어 Max가 지금 힘 64, 마법 44인 검을 가지고 있다면, Long Sword(40%)와 Great Sword(60%)에 Sword Twister를 써서 힘과 마법이 같은 Longish-Greatish Sword를 만들 수 있으므로 그 검을 팔 수 있다. Max는 Sword Twister를 원하는 만큼 여러 번 쓸 수 있다. 예를 들어 힘 36, 마법 0인 검도 가지고 있었다면, 이 검(50%)과 방금 만든 Longish-Greatish Sword(50%)에 Sword Twister를 써서 힘 50, 마법 22인 검을 만들 수 있다.
어떤 검이 팔 수 있고 Sword Twister를 여러 번 써서 힘과 마법이 정확히 같은 검을 만들 수 있으면, 그 검은 대체 가능하다고 한다. Max의 검 중 어느 것이 대체 가능한가?
입력
입력의 첫 줄에는 정수 n (1 ≤ n ≤ 200 000)이 주어지며, 이는 Max가 처음에 가지고 있는 검의 수이다.
다음 n개 줄은 검을 설명한다. 각 줄에는 정수 s (0 ≤ s ≤ 109)와 m (0 ≤ m ≤ 109)이 주어지며, 각각 그 검의 힘과 마법이다. n자루의 검은 모두 팔 수 있고, 힘과 마법이 정확히 같은 검은 두 자루도 없다.
출력
각 검의 대체 가능 여부를 입력 순서대로 공백 없이 한 줄에 출력한다. 대체 가능하면 Y, 그렇지 않으면 N을 출력한다.