排序+HASH,地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1974
#include <stdio.h>
#include 
<stdlib.h>

const int MAX = 131075;

typedef struct
{
    
int x;
    
int y;
    
int next;
}
point;


point p[MAX];
//多少个有石头的结点
int now;
struct
{
    
int next;//下一个
    int last;//最后一个的位置
}
hash[MAX];

void init ( int len )
{

    now 
= 0;
    
for ( int i=0; i<len; i++ )
    
{
        hash[i].next 
= -1;
        hash[i].last 
= -1;
    }

}


void add ( point *node )
{

    p[now].next 
= -1;
    p[now].x 
= node->x;
    p[now].y 
= node->y;

    
int head = node->x;
    
if ( hash[head].next == -1 )
    
{
        hash[head].next 
= now;
    }

    
else
    
{
        p[ hash[head].last ].next 
= now;
    }

    hash[head].last 
= now ++;
}


point num[MAX];

int cmpx ( const void *a, const void *b )//以X为主要排序策略
{

    
int ans = ( ( point * )a )->- ( ( point * )b )->x;
    
if ( ! ans )
    
{
        ans 
= ( ( point * )a )->- ( ( point * )b )->y;
    }


    
return ans;
}


int cmpy ( const void *a, const void *b )//以Y为主要排序策略
{

    
int ans = ( ( point * )a )->- ( ( point * )b )->y;
    
if ( ! ans )
    
{
        ans 
= ( ( point * )a )->- ( ( point * )b )->x;
    }


    
return ans;
}



int main ()
{

    
int t;
    
int n, m, k;
    
int i;

    scanf ( 
"%d"&t );
    
while ( t -- )
    
{
        scanf ( 
"%d%d%d"&m, &n, &k );
        
for ( i=0; i<k; i++ )
        
{
            scanf ( 
"%d%d"&num[i].x, &num[i].y );
            num[i].x 
--;
            num[i].y 
--;
        }


        
int count = 0;
        qsort ( num, k, sizeof ( point ), cmpy );
        init ( n );
        
for ( i=0; i<k; i++ )
        
{
            point node;
            node.x 
= num[i].y;
            node.y 
= num[i].x;
            add ( 
&node );
        }

        
for ( i=0; i<n; i++ )
        
{
            
if ( hash[i].next == -1 )
            
{
                count 
++;
            }

            
else
            
{
                
int temp = 0;
                
int j = hash[i].next;
                
if ( p[j].y - 0 > 1 )
                
{
                    count 
++;
                }

                
for ( j=hash[i].next; p[j].next!=-1; j=p[j].next )
                
{
                    
int nextj = p[j].next;
                    
if ( p[nextj].y - p[j].y > 2 )
                    
{
                        count 
++;
                    }

                }

                
if ( m-1 - p[j].y > 1 )
                
{
                    count 
++;
                }

            }

        }


        qsort ( num, k, sizeof ( point ), cmpx );
        init ( m );
        
for ( i=0; i<k; i++ )
        
{
            add ( 
&num[i] );
        }

        
for ( i=0; i<m; i++ )
        
{
            
if ( hash[i].next == -1 )
            
{
                count 
++;
            }

            
else
            
{
                
int temp = 0;
                
int j = hash[i].next;
                
if ( p[j].y - 0 > 1 )
                
{
                    count 
++;
                }

                
for ( j=hash[i].next; p[j].next!=-1; j=p[j].next )
                
{
                    
int nextj = p[j].next;
                    
if ( p[nextj].y - p[j].y > 2 )
                    
{
                        count 
++;
                    }

                }

                
if ( n-1 - p[j].y > 1 )
                
{
                    count 
++;
                }

            }

        }


        printf ( 
"%d\n", count );
    }

    
return 0;
}