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.

Leave a Reply

Your email address will not be published. Required fields are marked *