Woburn Challenge 2018-19 Round 2 - Senior Division
Problem 1: Laser Grid
The IMF (Impossible Mission Force) has dispatched their best agent, Ethan Hunt, to recover a recently stolen microchip. This microchip contains critical Canadian governmental secrets, such as the Prime Minister's favourite colour, and must be recovered before its captors have time to download its data!
Ethan has tracked the microchip down to an underground base in Saskatchewan. Upon infiltrating it, he's found himself in the middle of a gigantic, square room. When viewed from above, the room can be represented as a square on a 2D plane, with its bottom-left corner at coordinates (0, 0) and its top-right corner at coordinates (1,000,000, 1,000,000). Ethan has lowered himself down into the room, and is standing at coordinates (XE, YE) (1 ≤ XE, YE ≤ 999,999).
There are N (0 ≤ N ≤ 100,000) vertical lasers extending across the entire room, the i-th of which is a line segment from coordinates (Vi, 0) to (Vi, 1,000,000) (1 ≤ Vi ≤ 999,999). There are also M (0 ≤ M ≤ 100,000) horizontal lasers extending across the entire room, the i-th of which is a line segment from coordinates (0, Hi) to (1,000,000, Hi) (1 ≤ Hi ≤ 999,999). All vertical lasers have distinct V values, all horizontal lasers have distinct H values, and no laser goes directly through Ethan's location (in other words, no V value is equal to XE, and no H value is equal to YE).
Ethan was hoping to simply find the stolen microchip, but he's been greeted by a more troubling sight: there are C (1 ≤ C ≤ 100,000) microchips strewn about the room! The i-th microchip is at coordinates (Xi, Yi) (1 ≤ Xi, Yi ≤ 999,999). No two microchips are at the same location, no microchip is at Ethan's location, and no laser goes directly through any microchip's location.
One of these C microchips must be the real one, with the rest being decoys, but they all look identical! Unfortunately, Ethan will only have time to go grab at most one of them before getting out of there. To make matters even worse, Ethan may not pass through any lasers on his way to pick up the microchip of his choice, as they'd trigger an alarm. He'll need to weigh his options and choose his plan of action carefully!
For each microchip, determine whether or not Ethan would be able to reach its location from (XE, YE) by following any continuous path on the 2D plane (not necessarily a straight line segment), without leaving the confines of the room and without passing through any of the N + M lasers.
In test cases worth 5/13 of the points, each integer in the input is no greater than 10.
In test cases worth another 5/13 of the points, N ≤ 2000, M ≤ 2000, and C ≤ 2000.
The first line of input consists of two space-separated integers, XE and YE.
The next line consists of three space-separated integers, N, M, and C.
N lines follow, the i-th of which consists of a single integer, Vi, for i = 1..N.
M lines follow, the i-th of which consists of a single integer, Hi, for i = 1..M.
C lines follow, the i-th of which consists of two space-separated integers, Xi and Yi, for i = 1..C.
Output C lines with a single character per line, either "
Y" if Ethan would be able to reach the i-th microchip, or "
N" otherwise, for i = 1..C.
2 6 2 3 5 3 8 4 2 7 6 6 1 5 4 1 2 8 2 5
N Y N N Y
The room is illustrated below, with lasers indicated in red, Ethan's location in green, and the microchips in blue. Note that most of the x-coordinates and y-coordinates on the plane (from around 10 to around 999,997) have been collapsed together.
Ethan would only be able to reach the 2nd or 5th microchip.
Point Value: 7 (partial)
Time Limit: 3.00s
Memory Limit: 32M
Added: Dec 14, 2018
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3