3409. Rectilinear polygon

单点时限: 1.0 sec

内存限制: 256 MB

Given is $n$ points with integer coordinates in the plane. Is it is possible to construct a simple, that is non-intersecting, rectilinear polygon with the given points as vertices? In a rectilinear polygon there are at least $4$ vertices and every edge is either horizontal or vertical; each vertex is an endpoint of exactly one horizontal edge and one vertical edge. There are no holes in a polygon.

输入格式

The first line of input is an integer giving the number of cases that follow. The input of each case starts with an integer $4 \le n \le 100~000$ giving the number of points for this test case. It is followed by $n$ pairs of integers specifying the $x$ and $y$ coordinates of the points for this case.

输出格式

The output should contain one line for each case on input. Each line should contain one integer number giving the length of the rectilinear polygon passing throught the given points when it exists; otherwise, it should contain $-1$.

样例

Input
1
8
1 2
1 0
2 1
2 2
3 2
3 1
4 0
4 2
Output
12

0 人解决,1 人已尝试。

0 份提交通过,共有 1 份提交。

9.9 EMB 奖励。

创建: 2 年,9 月前.

修改: 2 年,9 月前.

最后提交: 1 年,9 月前.

来源: Waterloo local, 2006.9.30

题目标签