Under construction

Still being built. Things may change

Fence the vegetables

Time limit3sMemory limit256 MB

Summary
Given up to 100000 plant points, compute the perimeter and area of the smallest axis-aligned integer-corner fence that keeps each side 1 mm from every plant.
Level

Medium5 of 10

Topics
Geometry, Math
Solved
No attempts yet

Problem

Alice and Bob retired and took up gardening. They planted vegetables all over a huge field, and now the plants need protection from wild animals, so the two decided to build a fence around them.

The field is the XY plane, and each plant is a point in it. A fence is a polygon that meets all of the following conditions.

  • It is a simple polygon that neither touches nor crosses itself, and every side is parallel to one of the axes.
  • Every corner has integer coordinates. Coordinates are measured in millimeters.
  • Every plant lies inside the fence.
  • Every side of the fence is at least 11 millimeter away from every plant. The distance between a side and a plant is the Euclidean distance between the point and the segment.
  • Any two sides that are not adjacent are at least 11 millimeter apart.

To save fence material, Alice and Bob build the fence with the smallest perimeter among those that meet the conditions. If several fences share the smallest perimeter, they build the one with the smallest area among them, to save time when watering. Compute the perimeter and the area of that fence.

Input

The first line contains an integer VV (1≤V≤1051 \le V \le 10^5), the number of plants.

Each of the next VV lines contains two integers XX and YY (1≤X,Y≤1081 \le X, Y \le 10^8), the coordinates of one plant in millimeters. No two plants are at the same position.

Output

Print the perimeter PP of the fence in millimeters and its area AA in square millimeters on one line, separated by a space.

Examples3

  1. Example 1

    Input
    4
    1 1
    3 5
    5 3
    5 5
    
    Expected output
    24 21
    
  2. Example 2

    Input
    4
    1 1
    1 100000000
    100000000 1
    100000000 100000000
    
    Expected output
    400000004 10000000200000001
    
  3. Example 3

    Input
    5
    50000000 1
    50000000 99999999
    1 50000000
    99999999 50000000
    50000001 50000001
    
    Expected output
    400000000 399999997