zoj 3761

#include<cstdio>
#include<algorithm>
#include<cstring>
#define inf 1000000000
#define maxn 2009
using namespace std;

struct node
{
    int x;
    int y;
    int p;
    int sum;
    int son[5];
    bool operator <(const node &t)const
    {
        if(x==t.x)
            return y<t.y;
        else return x<t.x;
    }
} no[maxn];

int f[maxn];
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}

int dis(int a,int b)
{
    return(abs(no[a].x-no[b].x)+abs(no[a].y-no[b].y));
}

bool check(int a,int b)
{
    bool flag=1;
   if(no[a].x!=no[b].x&&no[a].y!=no[b].y)
        flag=0;
    if(find(b)==a)flag=0;
    if(no[b].sum>=4)flag=0;
    return flag;
}

void dfs(int root)
{
    for(int i=0;i<no[root].sum;i++)
        dfs(no[root].son[i]);
    if(no[root].p!=-1)
    {
       if(no[root].x==no[no[root].p].x)
        {
           if(no[root].y<no[no[root].p].y)
            {
               printf("(%d, %d) UP\n",no[root].x,no[root].y);
            }
            else printf("(%d, %d) DOWN\n",no[root].x,no[root].y);
        }
        else if(no[root].y==no[no[root].p].y)
        {
           if(no[root].x<no[no[root].p].x)
               printf("(%d, %d) RIGHT\n",no[root].x,no[root].y);
            else printf("(%d, %d) LEFT\n",no[root].x,no[root].y);
        }
    }
}

int main()
{
    int n;
    int tar,d;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0; i<n; i++)
        {
           scanf("%d%d",&no[i].x,&no[i].y);
            no[i].p=-1;
            f[i]=i;
            no[i].sum=0;
        }
        for(int i=0; i<n; i++)
        {
            d=inf;
            tar=-1;
            for(int j=0; j<n;j++)
            {
               if(i==j) continue;
               if(dis(i,j)<d&&check(i,j))
               {
                   d=dis(i,j);
                   tar=j;
               }
            }
           if(tar==-1){no[i].p=-1;continue;}
            no[i].p=tar;
            f[i]=tar;
            no[tar].son[no[tar].sum++]=i;
        }
        int ans=0;
        for(int i=0; i<n; i++)
           if(no[i].p==-1)
               ans++;
        printf("%d\n",ans);
        for(int i=0; i<n; i++)
        {
            if(no[i].p==-1)
               dfs(i);
        }
    }
    return 0;
}
/*
18
1 1
2 1
2 2
4 2
5 2
6 2
2 3
3 3
4 3
5 3
7 3
5 4
8 4
1 5
2 5
3 5
4 5
5 5
*/