Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

K. Kumquat Orchard
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Kumquats on a small tree. Image by Amalucan, Wikimedia Commons, License CC BY-SA 4.0.

Your orchard has a vole problem. Voles gnaw the bark off kumquat trees, and the county permit office recognizes only one defence: an enclosure with a buried mesh skirt. Permits are issued only for rectangular enclosures aligned with the cadastral grid (north–south and east–west). Each enclosure must be freestanding: fences may not cross or even touch. Trees must stand clear of the fence line, or the voles will nibble them right through the mesh.

There is one complication. At the centre of the orchard, at $$$(0, 0)$$$, lives a mole. The mole is not the problem: moles eat grubs, not kumquats, so your trees are safe from the furry neighbour's attention. But another municipal office has decided that moles are a protected species. In particular no fence may be built over, against, or around its molehill, since the mesh skirt that stops voles would trap it too.

The county supplies all building materials for works of arboreal protection, so an enclosure costs you nothing however much ground it takes in. Each permit, on the other hand, costs an exorbitant fee, so you want to build as few enclosures as you can. Show the permit office where the fences go.

Sample 2.

Input

The input consists of:

  • One line with an integer $$$n$$$ ($$$1 \leq n \leq 100\,000$$$), the number of kumquat trees.
  • $$$n$$$ lines, one per tree, each with two integers $$$x$$$ and $$$y$$$ ($$$-1000 \leq x, y \leq 1000$$$ and $$$(x, y) \neq (0, 0)$$$), the position of that tree.
No two trees stand at the same position.
Output

First output one line with an integer $$$k$$$ ($$$1 \leq k \leq n$$$), the smallest number of enclosures needed to protect every tree. Then output $$$k$$$ lines, one per enclosure, each with the four corners of that enclosure as eight numbers $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ $$$x_3$$$ $$$y_3$$$ $$$x_4$$$ $$$y_4$$$. The corners may be given in any order. Every coordinate must be written with exactly one digit after the decimal point, and have absolute value at most $$$2000.0$$$.

If there are multiple optimal solutions, you may output any one of them.

Examples
Input
1
2 3
Output
1
0.5 2.5 2.5 2.5 2.5 3.5 0.5 3.5
Input
5
1 0
-2 -2
1 -1
0 1
2 1
Output
3
-4.0 -4.0 -4.0 -1.0 -1.0 -1.0 -1.0 -4.0
0.5 -1.5 1.5 -1.5 0.5 0.3 1.5 0.3
-0.5 0.4 3.0 0.4 -0.5 2.0 3.0 2.0