A Study in Bake Street
All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Chef Ada is not just a Chef but also a detective. Currently she is investigating a massive murdering case in Bake Street.
Bake Street is composed of n buildings in a straight line. They are numbered from 1 to n, as you move from left to right. The i-th building is at position xi and has height hi. The buildings are so thin that we can consider them as vertical segments. The murderer climbed to the top of one of the buildings and shot at all the buildings to the right, which had a lesser height than the building on which he was, and which were in his line of sight.
Ada is interested in the rightmost building that was shot by the murderer. Since we don't know the building from which the murderer was shooting, your task is to calculate it for every possible initial position.
The first line of input contains one number T, the number of test cases. T test cases follows. The first line of each test case contains an integer n, the number of buildings. The next n lines contains two integers xi, hi. the position and height of the i-th building.
For each testcase print n integers: ai, the rightmost building shot at, if the murderer started at building i. If the murderer didn't shoot to any building, print -1.
Input: 1 7 1 130 65 110 120 40 160 60 240 100 280 65 320 30 Output: 5 5 -1 -1 7 7 -1
The lines of shooting are shown in the figure above.
From building 1, buildings 2 and 5 are shot. As the rightmost is building 5, that is the answer for building 1. Note that from building 1 is not possible to shoot at building 4 (dotted line) because building 2 obstructs the line of sight.
From building 2, buildings 3, 4 and 5 are shot. From building 3 and 4, no building is shot at. Hence the third and fourth outputs are -1.
|Tags||alei, convex, cook83, geometry, hull, medium, stack|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.