Two Cakes
Time limit1sMemory limit1024 MB
Given two rectangles, find a non-vertical line y=px+q that splits each rectangle into two pieces of equal area.
- Level
Medium6 of 10
- Topics
- Geometry, Math, Binary search
- Solved
- No attempts yet
Problem
SUAPC 2023 Summer problem setters were to be fed two-dimensional cakes delivered to room Gong A527 at Yonsei University. The setters were so hungry from writing problems that they ate all of them except two special cakes.
Sinchon ICPC and Morgorithm, who arrived late, avoided the setters' anger by offering them two unopened cake boxes. Looking at the cakes, they got an idea for a new problem: both cakes are rectangles. They proved that a single straight cut can split each cake into two pieces of equal area. The setters, now out of sugar, left it to the contest team to find where this cut should go.
Before the two of them finish eating the cakes, find a cut that splits each of the two cakes into two pieces of equal area.
Input
The first line to the fourth line each contain the x and y coordinates of a vertex of the first cake, separated by a space.
The fifth line to the eighth line each contain the x and y coordinates of a vertex of the second cake, separated by a space.
Each cake is always a non-empty rectangle, and the vertices of each cake are given in random order. The two cakes never meet at a single point, and no valid cut is parallel to the y-axis.
Output
If the cut is part of a straight line , print and on the first line, separated by a space. If there are multiple answers, print any of them.
If or is an integer, print it as is. If it is not an integer, and the number to print is , print and separated by '/'. are integers, ,
The calculation and output may exceed the range of 32-bit integers.