This page is still under construction.

Parts of this page are still being built. What you see may change.

Floor Painting

Time limit2sMemory limit256 MB

Summary
Find the side length of the largest axis-aligned square that fits inside a given orthogonal simple polygon.
Level

Hard8 of 10

Topics
Geometry, Binary search
Solved
No attempts yet

Problem

A museum wants a square painting on the floor of one of its exhibition rooms. Every wall of the room is straight, and two adjacent walls meet at a right angle. Two walls that are not adjacent never touch, and the room has no pillars, so the floor is a simple polygon whose sides are all parallel to the coordinate axes.

The painting is a square. Its four sides must be parallel to the walls, and the whole square must lie inside the floor. The square may touch a wall. The museum wants the painting as large as possible. Find the largest side length it can have.

Input

The first line contains the number of rooms TT (1≤T≤1001 \le T \le 100).

Each room is then given as follows.

  • one line with the number of corners nn (4≤n≤10004 \le n \le 1000)
  • nn lines, each with two integers xx and yy (0≤x,y≤100 0000 \le x, y \le 100\,000) separated by a space, the coordinates of one corner

The corners are given in clockwise order.

Output

For each room, print one line with a single integer: the largest side length of a square painting that fits on the floor.

Examples3

  1. Example 1

    Input
    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
    Expected output
    5
4
6

  2. Example 2

    Input
    1
4
0 0
0 1
1 1
1 0
    Expected output
    1

  3. Example 3

    Input
    3
12
0 2
0 3
2 3
2 5
3 5
3 3
5 3
5 2
3 2
3 0
2 0
2 2
12
0 3
0 6
3 6
3 9
6 9
6 6
9 6
9 3
6 3
6 0
3 0
3 3
12
0 14
0 21
14 21
14 35
21 35
21 21
35 21
35 14
21 14
21 0
14 0
14 14
    Expected output
    1
3
7