The 7th(2012) ACM Programming Contest of HUST - Onsite Contest(Semilive)
From: 2012-12-16 12:10:00
To: 2012-12-16 17:10:00
Now: 2017-09-24 21:42:24
G - Minimum Planar Graph
Time Limit: 3s
Memory Limit: 128MB
Submissions: 8 Solved: 1
- 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)
- 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)
- The minimum area of bounding rectangle.
- Sample Input
- Sample Output
- Picture of second example:
- The 7th(2012) ACM Programming Contest of HUST
Problem Setter: Jian He