先按规则连。规则是隔一段连一个。比如一条直线上有6个点,就1-2,3-4,5-6,这么连。如果只有奇数个点,就不行。然后再判有没有洞。
方法是任选一个点,走一圈,看看是否遍历所有的点。
#include <iostream>

using namespace std;

const int MAXN=100010;


typedef struct
{
int x,y,id;
} point_t;


int cmp_x(const point_t &a,const point_t &b)
{
return a.x<b.x || a.x==b.x && a.y<b.y;
}


int cmp_y(const point_t &a,const point_t &b)
{
return a.y<b.y || a.y==b.y && a.x<b.x;
}

point_t p[MAXN];
int c[MAXN][2];


int main()
{
int ca,n,i;

for (scanf("%d",&ca);ca--;)
{
scanf("%d",&n);

for (i=0;i<n;i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
p[i].id=i;
}
int ans=0,flag=1;
sort(p,p+n,cmp_x);
int cnt=1;

for (i=1;i<n;i++)
{

if (p[i].x!=p[i-1].x)
{
if (cnt&1) flag=0;
cnt=1;
}

else
{
cnt++;

if ((cnt&1)==0)
{
ans+=p[i].y-p[i-1].y;
c[p[i].id][0]=p[i-1].id;
c[p[i-1].id][0]=p[i].id;
}
}
}
sort(p,p+n,cmp_y);
cnt=1;

for (i=1;i<n;i++)
{

if (p[i].y!=p[i-1].y)
{
if (cnt&1) flag=0;
cnt=1;
}

else
{
cnt++;

if ((cnt&1)==0)
{
ans+=p[i].x-p[i-1].x;
c[p[i].id][1]=p[i-1].id;
c[p[i-1].id][1]=p[i].id;
}
}
}
//check connect
int p=1,x=0,cc=0;

do
{
x=c[x][p];
p=1-p;
cc++;
} while (x!=0);
if (cc!=n) flag=0;
if (!flag) printf("-1\n");
else printf("%d\n",ans);
}
return 0;
}