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