Cake Cuts

Time limit1sMemory limit128 MB

Summary
Given K, find the minimum number of straight full-square chord cuts needed so the cake splits into at least K pieces, and output coordinates for such cuts.
Level

Medium7 of 10

Topics
Math, Geometry, Greedy
Solved
No attempts yet

Problem

There is a square cake whose side length is 10 meters. You may make several straight cuts, and every cut must satisfy all of the following conditions.

  • Each cut starts at one point on the cake's perimeter and ends at another point on the perimeter.
  • A cut may not lie completely on one side of the square.
  • No two cuts may have both the same starting point and the same ending point.

The pieces are separated and counted only after all cuts have been made. While the cuts are being made, the outer shape of the cake remains the original square.

Find the minimum number of cuts needed to obtain at least K pieces, and output actual cuts that achieve it.

Input

The first line contains an integer K, the minimum required number of pieces.

1 <= K <= 1 000 000

Output

On the first line, output the minimum required number of cuts N.

On each of the next N lines, output four integers x1 y1 x2 y2, the starting and ending point of one cut.

Coordinates are measured in millimeters. Two opposite corners of the cake are (-5000, -5000) and (5000, 5000). Therefore every point (x, y) on the boundary of the square satisfies the following condition.

max(|x|, |y|) = 5000

Examples3

  1. Example 1

    Input
    1
    Expected output
    0

  2. Example 2

    Input
    4
    Expected output
    2
-5000 -5000 5000 5000
5000 -5000 -5000 5000

  3. Example 3

    Input
    7
    Expected output
    3
-5000 5000 0 -5000
-2000 -5000 5000 5000
-5000 0 5000 0