Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0035 - BAD SIGNAL

  There is an important UN meeting in town. Any self-respecting espionage agency will try to eavesdrop on the delegations to gain some advantage in the negotiations. They do this by planting hidden microphones in and around the meeting places. Those microphones contin- uously capture sound waves and transmit them via radio.

   In fact, fierce competition between espionage agencies has left the whole city scattered with hidden microphones, so much so that the radio waves interfere with each other and it is often not even possible to make out any signal in the mess of radio waves – depending on your position and proximity to the different transmitters obviously.

   Specifically, it is possible to make out a signal i if and only if:

 

 

   Where

  • ri=si/|Pi-Plisten|2 is the strength of the received signal of microphone i,
  • si is the strength of the signal sent from microphone i,
  • Pi is the position of microphone i,
  • Plisten is the position where you are listening to the signals,
  • |Pi Pj | is the Euclidean distance between points Pi and Pj and
  • B is the level of background noise.

Input

   On the first line one positive number: the number of test cases, at most 100. After that per test case:

  • one line with an integer n (0 n 100 000): the number of planted microphones.
  • one line with the integer B (0 B 1 000 000): the level of background noise.
  • one line with two space-separated integers x and y: the x and y coordinates of the loca- tion Plisten where you receive the signals.
  • n lines with three space-separated integers xi, yi and si (0 < si 1 000 000): the x and y coordinates of the location Pi of microphone i and its signal strength, respectively.

   All coordinates are in the range [0; 10 000]. The locations Pi all differ from Plisten. The test data is constructed so that small floating point rounding errors will not influence the outcome of any solution.

Output

   Per test case:

  • one line with an integer: the (one-based) index of a microphone, the signal of which can be made out, or the string “NOISE” if there is no such microphone.

Examples

stdin

stdout

1

3

4

10

100 100

90 90 20000

110 90 50

90 110 1000

110 110 50

4

100

100 100

90 90 20000

110 90 50

90 110 1000

110 110 50

2

0

0 10

0 0 1000

0 8 1

1

NOISE

1


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2013-12-21
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Benelux Preliminary (BAPC) 2013.B

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.