# Poj Solution 1974

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;
}

This entry was posted in poj. Bookmark the permalink.