USACO 2013 January Contest, Bronze

Problem 1. Mirrors

Contest has ended.

Log in to allow submissions in analysis mode

Problem 1: Mirrors [Brian Dean and Travis Hance, 2013] Farmer John's cows have been causing too much trouble around the farm, and FJ therefore wants to keep a more watchful eye on them. By installing N reflective fences (1 <= N <= 200) at various locations on the farm, he hopes to be able to see from his house at location (0,0) to the barn at location (a,b). On a 2D map of FJ's farm, fence i appears as a short line segment centered at integer location (x_i, y_i) and tilted 45 degrees (either like '/' or like '\'). For example, a fence oriented like '/' at position (3,5) could be described as a line segment from (2.9,4.9) to (3.1,5.1). Each fence (and also the location of the barn) lies at a different position with integer coordinates in the range -1,000,000...1,000,000. No fence lies at (0,0) or (a,b). FJ plans to sit at his house at position (0,0) and look directly to the right (in the +x direction). With his gaze bouncing off some of the reflective fences on his farm, he hopes to be able to see the point (a,b). Unfortunately, FJ thinks he oriented one of his fences incorrectly (e.g., '\' instead of '/'). Please output the index of the first fence in FJ's list such that by toggling its direction (between '/' and '\' or vice versa), FJ will be able to see the point (a,b). If FJ can already see the point (a,b) without toggling any fence, please output 0. If it is still impossible for him to see (a,b) even after toggling up to a single fence, output -1. PROBLEM NAME: mirrors INPUT FORMAT: * Line 1: Three space-separated integers, N, a, and b. * Lines 2..1+N: Line i+1 describes fence i and contains either "x_i y_i /" or "x_i y_i \", where (x_i, y_i) is the location of the center of the fence, and \ or / refers to its orientation. SAMPLE INPUT (file 5 6 2 3 0 / 0 2 / 1 2 / 3 2 \ 1 3 \ INPUT DETAILS: A map of the farm looks like this (with H denoting FJ's house and B denoting the barn): 3 .\..... 2 //.\..B 1 ....... 0 H../... 0123456 OUTPUT FORMAT: * Line 1: The index of the first fence for which toggling that fence allows FJ to see the point (a,b). If FJ can already see the point (a,b), please output 0, or if there is no way he can see (a,b) even after toggling up to one fence, please output -1. SAMPLE OUTPUT (file mirrors.out): 4 OUTPUT DETAILS: By toggling the fence at position (3,2), FJ can see the point (a,b). On the map: 3 .\..... 2 //./--B 1 ...|... 0 H--/... 0123456
Contest has ended. No further submissions allowed.