pku1974.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>

typedef struct 
{
	int x, y;
} Point;

Point p[200001];

int cmp1(const void *a, const void *b)
{
	Point *c = (Point *)a;
	Point *d = (Point *)b;

	if (c->x != d->x)
	{
		return c->x - d->x;
	}
	else
	{
		return c->y - d->y;
	}
}

int cmp2(const void *a, const void *b)
{
	Point *c = (Point *)a;
	Point *d = (Point *)b;

	if (c->y != d->y)
	{
		return c->y - d->y;
	}
	else
	{
		return c->x - d->x;
	}
}


int main()
{
	int m, n, k, t, i, sum;

	scanf("%d", &t);

	while (t--)
	{
		scanf("%d%d%d", &m, &n, &k);

		if (k == 0)
		{
			printf("%d\n", m + n);
			continue;
		}
		
		for (i = 0; i < k; i++)
		{
			scanf("%d%d", &p[i].x, &p[i].y);
		}

		sum = 0;
//	The First Time, X come First		
		qsort(p, k, sizeof(p[0]), cmp1);

		sum += p[0].x - 1;

		sum += m - p[k-1].x;

		if (p[0].y > 2)
		{
			sum++;
		}

		if (n - p[k-1].y >= 2)
		{
			sum++;
		}

		for (i = 0; i < k - 1; i++)
		{
			if (p[i].x == p[i+1].x)
			{
				if (p[i+1].y - p[i].y > 2)
				{
					sum++;
				}
			}
			else
			{
				sum += p[i+1].x - p[i].x -1;
				
				if (n - p[i].y >= 2)
				{
					sum++;
				}
				if (p[i+1].y > 2)
				{
					sum++;
				}
			}
		}
//	The second Time
		qsort(p, k, sizeof(p[0]), cmp2);
		
		sum += p[0].y - 1;

		sum += n - p[k-1].y;

		if (p[0].x > 2)
		{
			sum++;
		}

		if (m - p[k-1].x >= 2)
		{
			sum++;
		}

		for (i = 0; i < k - 1; i++)
		{
			if (p[i].y == p[i+1].y)
			{
				if (p[i+1].x - p[i].x > 2)
				{
					sum++;
				}
			}
			else
			{
				sum += p[i+1].y - p[i].y -1;

				if (m - p[i].x >= 2)
				{
					sum++;
				}
				if (p[i+1].x > 2)
				{
					sum++;
				}
			}
		}
		printf("%d\n", sum);
	}

	
	return 0;
}