http://poj.org/problem?id=1974
#include<stdio.h>
#include<stdlib.h>
#define debug 0
#define NMAX 1000003
struct data
{
long x,y;
}v[NMAX];
long t,m,n,k;
long count;
int cmp1(void const *a,void const *b)
{
if((*(struct data*)a).y==(*(struct data*)b).y)
return (*(struct data*)a).x-(*(struct data*)b).x;
else
return (*(struct data*)a).y-(*(struct data*)b).y;
}
int cmp2(void const *a,void const *b)
{
if((*(struct data*)a).x==(*(struct data*)b).x)
return (*(struct data*)a).y-(*(struct data*)b).y;
else
return (*(struct data*)a).x-(*(struct data*)b).x;
}
void solve()
{
int i;
qsort(v,k,sizeof(struct data),cmp1);
int sum=0;
// cy=v[0].y;
if(v[0].x>2)
sum++;
sum+=v[0].y-1;
for(i=1;i<k;i++)
{
if(v[i].y==v[i-1].y)
{
if(v[i].x-v[i-1].x>2)
sum++;
}
else
{
sum+=v[i].y-v[i-1].y-1;
if(n+1-v[i-1].x>2)
sum++;
if(v[i].x>2)
sum++;
}
}
if(n+1-v[i-1].x>2)
sum++;
sum+=m-v[i-1].y;
qsort(v,k,sizeof(struct data),cmp2);
if(v[0].y>2)
sum++;
sum+=v[0].x-1;
for(i=1;i<k;i++)
{
if(v[i].x==v[i-1].x)
{
if(v[i].y-v[i-1].y>2)
sum++;
}
else
{
sum+=v[i].x-v[i-1].x-1;
if(m+1-v[i-1].y>2)
sum++;
if(v[i].y>2)
sum++;
}
}
if(m+1-v[i-1].y>2)
sum++;
sum+=n-v[i-1].x;
printf("%dn",sum);
}
int main()
{
#if debug
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&m,&n,&k);
int p=0;
for(i=0;i<k;i++)
{
int t1,t2;
scanf("%d%d",&t1,&t2);
// if(t1<=m&&t2<=n&&t1>=1&&t2>=1)
// {
v[p].x=t2;
v[p].y=t1;
p++;
// }
}
k=p;
solve();
}
#if debug
fclose(stdin);
fclose(stdout);
#endif
return 1;
}