Each cow has a point and a broadcast radius; find the starting cow whose one-way reachable set is largest.
Medium4GraphDFSGeometryNo attempts yetTime limit2sMemory limit512 MBFarmer John's N cows (1≤N≤200) want to build an emergency broadcast system so they can pass important news to each other.
Instead of mooing across long distances, the cows equip themselves with walkie-talkies, one per cow. Each walkie-talkie has a limited transmission radius: a walkie-talkie of power P can transmit only to cows at distance P or less. The powers differ from cow to cow, so cow A may be able to transmit to cow B while cow B cannot transmit back to cow A. The cows can relay a message along a path of several hops, so not every cow needs to transmit directly to every other cow.
Because transmission can work in one direction only, the number of cows that receive the news depends on which cow starts the broadcast, once relaying is taken into account. Find the largest number of cows a broadcast from a single cow can reach.
The distance between two cows is the Euclidean distance.
The first line contains N.
Each of the next N lines contains the x coordinate and the y coordinate of one cow, followed by p, the power of the walkie-talkie that cow holds. All three values are integers between 0 and 25,000 inclusive.
Print on a single line the largest number of cows a broadcast from a single cow can reach. The cow that starts the broadcast is included in this number.