同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21154_Rectilinearpolygon

2022-5-16 18:18| 发布者: Hocassian| 查看: 49| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504938679200-Problem List-采集的数据-后羿采集器.html

Pro.ID

21154

Title

Rectilinear polygon

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21154

AC

Submit

Ratio

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

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 ≤ n ≤ 100000 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.

输出

Description

Input

Output

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.

Sample Input

1
8
1 2
1 0
2 1
2 2
3 2
3 1
4 0
4 2

Sample Output

Source

Waterloo local 2006.9.30