Fence the vegetables
Time limit3sMemory limit256 MB
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.
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 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 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 (), the number of plants.
Each of the next lines contains two integers and (), the coordinates of one plant in millimeters. No two plants are at the same position.
Output
Print the perimeter of the fence in millimeters and its area in square millimeters on one line, separated by a space.