The 7th(2012) ACM Programming Contest of HUST  Onsite Contest(Semilive)
From: 20121216 12:10:00
To: 20121216 17:10:00
Now: 20170924 21:42:24
Status: Public
G  Minimum Planar Graph
Time Limit: 3s
Memory Limit: 128MB
Submissions: 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