New update is available. Click here to update.

Two Squares

Posted: 26 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given two squares on a two-dimensional plane. The sides of the squares are parallel to the X and Y-axis. Your task is to find a line that would cut these two squares in exactly half. By exactly half, we mean the line should cut the square in two parts such that the area of both the parts is exactly the same.

Each square is represented by an array of four points, where each point has two integers denoting the x-coordinate and the y-coordinate, respectively. So, your task is to return an array of two numbers of type double, where the first number represents the slope, and the second number represents the y-intercept of the line. If such a line doesn’t exist, or multiple such lines exist, then return {-1, -1}. If the line is parallel to the Y-axis, then return {0,0}.

For Example:
If square s1 = {{0, 2}, {2, 2}, {2, 0}, {0, 0}} and square s2 = {{4, 2}, {6, 2}, {6, 0}, {4, 0}}.

squares

So, the two squares are shown in the above figure. The line that would cut these two squares in half has the equation y = 1. So the slope of the line is 0, and the y-intercept is 1. So, we return {0, 1} as the answer.
Input format:
The first line contains an integer ‘T', which denotes the number of test cases or queries to be run. Then, the T test cases follow.

Four lines follow. Each line contains two space-separated integers, denoting the x and y-coordinates of vertices of the square s1 in clockwise order starting from the top left corner.

Then the next four lines follow. Each line contains two space-separated integers, denoting the x and y-coordinates of vertices of the square s2 in clockwise order.
For more clarity, please refer to the sample inputs.
Output format:
For each test case, print a single line containing two space-separated numbers of type doubles denoting the slope and the y-intercept of the line, respectively, that would cut the squares in exactly half. 

Your answer will be considered correct if the absolute or relative error of the numbers doesn’t exceed 10^-6.

The output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5000
-100 <= x-coordinate, y-coordinate of both squares <= 100

Time limit: 1 second