先按規(guī)則連。規(guī)則是隔一段連一個(gè)。比如一條直線上有6個(gè)點(diǎn)，就1-2，3-4，5-6，這么連。如果只有奇數(shù)個(gè)點(diǎn)，就不行。然后再判有沒(méi)有洞。
方法是任選一個(gè)點(diǎn)，走一圈，看看是否遍歷所有的點(diǎn)。
#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;
}