DCP-24: Water Supply Back to All Problems

Hard Geometry > Basic Geometry

In a country called “Aqua”, there are two major cities, located on a cartesian plane with coordinates {x1,y1} and {x2,y2}. There is also a river which is lying right over the x-axis. This river provides the two cities with necessary water. The two cities are above the river on the cartesian plane, meaning, ( y1,y2 > 0 ). Using water directly from river will be harmful for the citizen. Thus, the government of country Aqua has decided to build a water treatment facility near the river. The exact position of the facility has not been decided yet, but it has been decided that the facility will be so near to the river that it’s y-coordinate can be assumed to be 0. So for now, lets assume, the facility is located at {x3,0}. Now, once the facility is built, water will be supplied from there to the cities using pipes. The cost of building pipes between two point is the distance between them. So, the government wants to build the facility at such a point that the cost of building pipes from the facility to the two cities is minimum. ![enter image description here][1] Given the location of the two cities, find the value of x3. Input: ------ First line will contain a single integer T (T<10000) indicating number of test case. After that, T lines will follow with four positive integers x1, y1, x2, y2 ( x1, y1, x2, y2 <= 10^6 ). Output: ------- For each case, print the case number, and then the value of x3 in a/b irreducible format. See the sample output for more details. Sample Input ------------ 2 2 2 4 2 2 2 4 3 Sample Output ------------- Case 1: 3/1 Case 2: 14/5 [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/e4683aeb-a918-c1ba-97f3-08d2e27f0170_333b6d3f9e224bcea1bdbcbdd2655ce2_W402xH302.png

Problem Setter:

Mohammad Samiul Islam

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats




# User Language Timing
01 jalal Cpp14 0.01s
02 tanvirzawad Cpp14 0.01s
03 feodorv Cpp14 0.02s
04 tariqiitju Cpp14 0.03s
05 RandyWaterhouse Python3 0.13s

Your feedback is our precious!

Or call +88 02 9853138 for support