1613 - Minimum Planar Graph

Time Limit : 3 Second

Memory Limit : 128 MB

Submission: 8

Solved: 1

Description
A planar graph is a graph that you can draw without having any edges crossing. Now we want you construct a planar graph that vertices are drawn on lattice points and edges are drawn as the straight lines between connected vertices.

 

To make the problem harder, we require the constructed planar graph with minimum bounding rectangle area. (Bounding rectangle means a rectangle that contains all vertices of planar graph)

 

Input
There are multiple cases ended with EOF. In each case, the first integer N represents the number of vertices, then followed by N*N matrix with 0 or 1 that specify the adjacent relation of each pair of vertices.

(N < 8 and the number of cases < 8)

 

Output
The minimum area of bounding rectangle.

 

sample input
3
010
100
000
7
0111111
1011101
1100001
1100100
1101011
1000101
1110110
sample output
0
15
hint
Picture of second example:

source
The 7th(2012) ACM Programming Contest of HUST Problem Setter: Jian He
© 2015 HUST ACMICPC TEAM. All Right Reserved.