B. Triangles on a Rectangle
A rectangle with its opposite corners in
You are given a list of lattice points such that each point lies on a side of a rectangle but not in its corner. Also, there are at least two points on every side of a rectangle.
Your task is to choose three points in such a way that:
- exactly two of them belong to the same side of a rectangle;
- the area of a triangle formed by them is maximum possible.
Print the doubled area of this triangle. It can be shown that the doubled area of any triangle formed by lattice points is always an integer.
The first line contains a single integer
The first line of each testcase contains two integers
The next two lines contain the description of the points on two horizontal sides. First, an integer
The next two lines contain the description of the points on two vertical sides. First, an integer
The total number of points on all sides in all testcases doesn't exceed
For each testcase print a single integer — the doubled maximum area of a triangle formed by such three points that exactly two of them belong to the same side.
3 5 8 2 1 2 3 2 3 4 3 1 4 6 2 4 5 10 7 2 3 9 2 1 7 3 1 3 4 3 4 5 6 11 5 3 1 6 8 3 3 6 8 3 1 3 4 2 2 4
25 42 35
The points in the first testcase of the example:
(1,0) ,(2,0) ;(2,8) ,(3,8) ,(4,8) ;(0,1) (0,4) ,(0,6) ;(5,4), (5,5) .
The largest triangle is formed by points
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.