zoj 3761 Easy billiards

这题的意思是，如果有限次的击球，根据题目给出的规则，桌上最少剩几个球。

看到题目的时候，我就想到树。如果以一个结点为根，和他上下左右最近的4个坐标为他的儿子，那么这样递归构造一棵树以后。那么有几棵树最后就是剩几个球。击球步骤的话，从每个叶子结点开始向父亲结点击球，直到最后剩下每棵树的根节点。

#include <iostream>
#include<stdio.h>
#define INF 1000000000

using namespace std;
typedef struct node
{
    int x,y;
    int visit;
    int son[4]; //分别记录上下左右四个儿子
    int fa; //记录父亲
} Node;

Node a[2010];
int n;

int dis(int n1,int n2)  //计算两个球距离的平方
{
    return (a[n1].x - a[n2].x) * (a[n1].x - a[n2].x) + ( a[n1].y - a[n2].y) * ( a[n1].y - a[n2].y);
}

int relation(int n1,int n2,int no) //父亲结点和儿子结点建立关系
{
    a[n1].son[no] = n2;
    a[n2].fa = n1;
}

void dfs(int cur)
{
    int min_up = INF,min_down = INF,min_left = INF,min_right = INF;
    int temp_up = -1,temp_down = -1,temp_left = -1,temp_right = -1; //存离该节点上下左右最近的四个节点编号
    for(int i = 0 ; i < n; i++)
    {
        if(i == cur) continue;
        if(a[i].visit == 0 && a[i].x == a[cur].x && a[i].y > a[cur].y && dis(cur,i) < min_up )
        {
            min_up = dis(i,cur);
            temp_up = i;
        }
        if(a[i].visit == 0 && a[i].x == a[cur].x && a[i].y < a[cur].y && dis(cur,i) < min_down)
        {
            min_down = dis(i,cur);
            temp_down = i;
        }
        if(a[i].visit == 0 && a[i].y == a[cur].y && a[i].x < a[cur].x && dis(cur,i) < min_left)
        {
            min_left = dis(i , cur);
            temp_left = i;
        }
        if(a[i].visit == 0 && a[i].y == a[cur].y && a[i].x > a[cur].x && dis(cur,i) < min_right)
        {
            min_right = dis(i , cur);
            temp_right = i;
        }
    }
    a[temp_up].visit = a[temp_down].visit = a[temp_left].visit = a[temp_right].visit = 1;
    if(temp_up != -1)
    {
        relation(cur,temp_up,0);
        dfs(temp_up);
    }
    if(temp_down != -1)
    {
        relation(cur,temp_down,1);
        dfs(temp_down);
    }
    if(temp_left != -1)
    {
        relation(cur,temp_left,2);
        dfs(temp_left);
    }
    if(temp_right != -1)
    {
        relation(cur,temp_right,3);
        dfs(temp_right);
    }
}

void dfs_print(int cur)
{
    for(int i = 0 ; i < 4; i++)
    {
        if(a[cur].son[i] != -1)
        {
            dfs_print(a[cur].son[i]);
            int temp = a[cur].son[i];
            if(i == 0) printf("(%d, %d) DOWN\n",a[temp].x,a[temp].y);
            if(i == 1) printf("(%d, %d) UP\n",a[temp].x,a[temp].y);
            if(i == 2) printf("(%d, %d) RIGHT\n",a[temp].x,a[temp].y);
            if(i == 3) printf("(%d, %d) LEFT\n",a[temp].x,a[temp].y);
        }

    }
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i = 0 ; i < n; i++)
        {
            scanf("%d %d",&a[i].x,&a[i].y);
            a[i].visit = 0;
            a[i].fa = i;
            for(int j = 0; j < 4; j++)
                a[i].son[j] = -1;
        }
        int ans = 0;
        for(int i = 0 ; i < n; i++)
        {
            if(!a[i].visit)
            {
                a[i].visit = 1;
                dfs(i);
                ans++;
            }
        }
        printf("%d\n",ans);
        for(int i = 0 ; i < n; i++)
        {
            if(a[i].fa == i)
            {
                dfs_print(i);
            }
        }
    }
    return 0;
}