EllysIncinerator
TCO20 North America Qualifier · 2020-09-19 · by espr1t
TCO20 North America Qualifier · 2020-09-19 · by espr1t · Geometry, Search
Problem Statement
Problem Statement
The government of the country, where Elly lives, thinks that the air there is too clean. To fix this, they want to build an incinerator, which burns waste.
For some unknown reason, the citizens started protesting. They had the absurd claim that the country was already burning enough coal and waste in its thermal power stations. Now the government thinks how to realize its project without making too much noise.
We can represent the country as a square 1000 by 1000 kilometers. There are several thermal power plants (TPS) inside it, which we'll represent as points with coordinates (X[i], Y[i]), laying inside or on the borders of this square. The TPS have different capacities. We'll consider the smoke cloud generated by each of them as a circle with radius R[i] and center the point (X[i], Y[i]). Since people have protested before because of the polu⦠clean air, the TPS are built in such a way that the smoke clouds of no two of them overlap (they are allowed to touch though).
Now the government has decided that if they make the incinerator follow the same rules people would stop protesting. For that, they need to find such a position and capacity for it, so its smoke cloud would not overlap with the smoke cloud of any of the TPS. Of course, they want the incinerator to be as powerful as possible, thus its radius should be as large as possible. Its coordinates should be inside or on the border of the country, however its smoke cloud (as well as the smoke clouds of the TPS) can go outside it.
You are given thedouble[] s X, Y and R giving the coordinates and the radius of each of the TPS. Return the maximum radius of the incinerator if positioned optimally.
For some unknown reason, the citizens started protesting. They had the absurd claim that the country was already burning enough coal and waste in its thermal power stations. Now the government thinks how to realize its project without making too much noise.
We can represent the country as a square 1000 by 1000 kilometers. There are several thermal power plants (TPS) inside it, which we'll represent as points with coordinates (X[i], Y[i]), laying inside or on the borders of this square. The TPS have different capacities. We'll consider the smoke cloud generated by each of them as a circle with radius R[i] and center the point (X[i], Y[i]). Since people have protested before because of the polu⦠clean air, the TPS are built in such a way that the smoke clouds of no two of them overlap (they are allowed to touch though).
Now the government has decided that if they make the incinerator follow the same rules people would stop protesting. For that, they need to find such a position and capacity for it, so its smoke cloud would not overlap with the smoke cloud of any of the TPS. Of course, they want the incinerator to be as powerful as possible, thus its radius should be as large as possible. Its coordinates should be inside or on the border of the country, however its smoke cloud (as well as the smoke clouds of the TPS) can go outside it.
You are given the
Notes
- Your return value will be considered correct if it has relative or an absolute error of less than 1e-9.
Constraints
- X, Y and R will contain between 2 and 100 elements, inclusive.
- X, Y and R will contain the same number of elements.
- Each element of X and Y will be between 0 and 1000, inclusive.
- Each element of R will be between 1 and 1414, inclusive.
- All the input circles will not overlap, but may touch.
Examples
0)
{42.1337, 543.21, 987.987, 0, 666.666, 133.331, 888.8}
{13.666, 765.432, 666.666, 1000, 66.66, 666.666666666, 88.8}
{191.17, 55.555, 321.321, 100, 16.6, 123.321, 8.8}
Returns: 320.33719645669953
The answer is achieved with the incinerator being at coordinates (434.939950686, 341.298204535).
1)
{0, 1000}
{0, 1000}
{666, 666}
Returns: 334.0000000000005
Two termal plants at the opposite corners of the country.
2)
{0, 550}
{0, 700}
{666, 5}
Returns: 535.8326913195992
3)
{0, 550}
{0, 800}
{666, 5}
Returns: 493.1812989815517
4)
{123, 808}
{497, 505}
{42, 17}
Returns: 577.9142674597779
Submissions are judged against all 27 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EllysIncinerator with a public method double getMax(vector<double> X, vector<double> Y, vector<double> R) · 27 test cases · 2 s / 256 MB per case