Counting Intersections

Time limit1sMemory limit128 MB

Summary
Given pairs of boundary points on a rectangle, determine the minimum total crossings needed to connect each pair with a curve inside the rectangle, and the largest crossing count on one curve among optimal drawings.
Level

Hard8 of 10

Topics
Graph, Combinatorics, Greedy
Solved
No attempts yet

Problem

Several points lie on the sides of a rectangle. Each shape appears at exactly two points, and no point lies on a vertex. For every shape, connect its two points with a straight or curved line that stays inside the rectangle. Connections may cross, but three or more connections must not meet at one point.

Find the smallest possible total number of crossing points. Also find, among drawings that achieve that minimum, the largest number of crossing points on any one connection.

A point is written as (s, d). Side 1 is the top side, 2 the bottom side, 3 the left side, and 4 the right side. On the top or bottom side, d is the distance from the left vertex. On the left or right side, d is the distance from the upper vertex.

Input

The first line contains the number of points N (N <= 50). Because each shape appears exactly twice, the next N / 2 lines describe one pair of equal-shaped points.

Each of those lines contains four integers s1 d1 s2 d2, representing the two points (s1, d1) and (s2, d2). All point positions are distinct. Every integer is positive, and every distance value is at most 50.

Output

Print the minimum possible total number of crossing points on the first line.

On the second line, print the maximum number of crossing points that any single connection has when the total number of crossings is minimized.

Examples1

  1. Example 1

    Input
    10
3 5 4 7
1 7 2 8
2 4 2 7
2 6 4 4
1 5 3 3
    Expected output
    4
3