Limits 1s, 512 MB

You are given two convex polygons made out of lattice points (integer coordinates). One of them is completely inside the other one. You have to create another convex polygon that separates the two. The intermediate convex polygon may contain real coordinates but should not contain more than 2 digits after the decimal point.

In other words, build a convex polygon that is completely inside the outer convex polygon and completely outside the inner convex polygon with fulfilling the above constraints. See the figures for a better understanding.

Please, refer to the note section for the definition of a convex polygon and what it means to be strictly inside of a convex polygon.


The first line contains two integers nn and mm where, 3n,m30.3 \leq n, \, m \leq 30.

The following nn lines each contain two integers xx and yy representing a point of the outer convex polygon.

Then, the following mm lines each contain two integers xx and yy representing a point of the inner convex polygon.

Each point coordinate range is 0x,y1040 \leq x, y \leq 10^4.

Points will be given in a counter-clockwise order for each convex polygon.


Print an integer pp representing the number of points in the new convex polygon. pp must be at least 33 and not greater than 10001000.

In the following pp lines, print the points in counter-clockwise order, forming a valid convex polygon, fulfilling all the requirements in the statement.

Note that, output containing more than 2 digits after the decimal point will receive a wrong answer verdict.


4 4
0 0
10 0
10 10
0 10
5 1
9 5
5 9
1 5
0.56 0.65
9.35 0.85
9.64 9.00
0.8 9.8

  • A convex polygon is a simple polygon where all its interior angles are strictly less than 180 degrees.

  • A convex polygon is considered completely inside of another convex polygon, when each and every point of the inner polygon is strictly inside of the outer convex polygon. Points on the border of the edges are not considered as strictly inside.


Login to submit.


85% Solution Ratio
steinumEarliest, Jan '23
TrAdBuFastest, 0.0s
TrAdBuLightest, 4.9 MB
abid1729Shortest, 1267B
Toph uses cookies. By continuing you agree to our Cookie Policy.