2743468_ac_93ms_596k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

struct node
{
	int id, tag;
	int x, y;
	int h, v;
}pot[100001];

bool cmpx(struct node a,struct node b)
{
	if (a.x==b.x)
		return a.y < b.y;
	else
		return a.x < b.x;
}

bool cmpy(struct node a,struct node b)
{
	if (a.y==b.y)
		return a.x < b.x;
	else
		return a.y < b.y;
}

bool cmpid(struct node a,struct node b)
{
	return a.id < b.id;
}

int main()
{
	int t, n, i, j, k, no, len, cnt;

	scanf("%d",&t);
	while (t--)
	{
		scanf("%d",&n);
		for (i = 0; i < n; i++)
			scanf("%d%d",&pot[i].x,&pot[i].y),pot[i].id = i,pot[i].tag = 0;
		sort(pot,pot+n,cmpx);
		i = len = 0;
		while(i < n)
		{
			j = i;no = 0;
			while(pot[j].x==pot[i].x)
				j++,no++;
			if(no%2)
			{
				printf("-1\n");
				goto loop;
			}
			for (k = i; k < j; k+=2)
			{
				pot[k].v = pot[k+1].id;
				pot[k+1].v = pot[k].id;
				len += pot[k+1].y-pot[k].y;
			}
			i = j;
		}
		sort(pot,pot+n,cmpy);
		i = 0;
		while(i < n)
		{
			j = i;no = 0;
			while(pot[j].y==pot[i].y)
				j++,no++;
			if(no%2)
			{
				printf("-1\n");
				goto loop;
			}
			for (k = i; k < j; k+=2)
			{
				pot[k].h = pot[k+1].id;
				pot[k+1].h = pot[k].id;
				len += pot[k+1].x-pot[k].x;
			}
			i = j;
		}
		sort(pot,pot+n,cmpid);
		j = 0, cnt = 0;
		while(1)
		{
			if(pot[j].tag==1)
				break;
			pot[j].tag = 1;
            if(cnt%2==0) 
				j = pot[j].h;
			else
				j = pot[j].v;  
            cnt++;
		}
		if(cnt==n)
			printf("%d\n",len);
		else
			printf("-1\n");
loop:
		;
	}
	return 0;
}