시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 11 | 5 | 5 | 50.000% |
The museum of Bizarre Argentinean Pocket Calculators (BAPC) has found a great painter to make a nice floor painting for in the museum. All walls in the museum are straight, and any two adjacent walls meet at a right angle. All non-adjacent walls are pairwise disjoint. Furthermore, the room in which the painting is supposed to come has no pillars. Hence, it is a rectilinear simple polygon.
The design for the painting is square. The museum wants the painting to be as large as possible. Furthermore, it should be placed such that the edges of the square are parallel to the walls. Find the maximum possible width for the painting.
On the first line one positive number: the number of test cases, at most 100. After that per test case:
The corners are given in clockwise order.
Per test case:
3 6 0 8 5 8 5 4 8 4 8 0 0 0 4 0 4 4 4 4 0 0 0 14 4 8 12 8 12 6 14 6 14 8 16 8 16 3 8 3 8 0 0 0 0 6 3 6 3 7 4 7
5 4 6
Floor plan of the first sample input with a 5 × 5 painting.