zoj3761 Easy billiards

点击打开链接

首先建图，两点若能碰撞就连一条边，会有多个连通分量，一个连通分量可以最后转化为一个点，把每个连通分量转化成树，从叶子节点向上，即用每个节点碰撞它的父节点，一个dfs就能解决。

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#define inf 1000000000
#define pi acos(-1.0)
#define eps 1e-8
#define seed 131
using namespace std;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long long ll;
const int maxn=100005;
int n;
int d[2005][2];
vector<int>g[2005];
bool vis[2005];
int ans;
struct node
{
    int p,q;
    node(int a,int b):p(a),q(b){}
};
vector<node>vec;
void dfs(int u,int fa);
int main()
{
    while(~scanf("%d",&n))
    {
        vec.clear();
        ans=0;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
            g[i].clear();
        for(int i=0;i<n;i++)
            scanf("%d%d",&d[i][0],&d[i][1]);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==j)
                    continue;
                if(d[i][0]==d[j][0]||d[i][1]==d[j][1])
                    g[i].push_back(j);
            }
        }
        for(int i=0;i<n;i++)
        {
            if(vis[i]==0)
                dfs(i,-1);
        }
        int len=vec.size();
        cout<<n-len<<endl;
        for(int i=0;i<len;i++)
        {
            int a=vec[i].p;
            int b=vec[i].q;
            if(d[a][0]==d[b][0])
            {
                if(d[a][1]<d[b][1])
                    printf("(%d, %d) UP\n",d[a][0],d[a][1]);
                else
                    printf("(%d, %d) DOWN\n",d[a][0],d[a][1]);
            }
            if(d[a][1]==d[b][1])
            {
                if(d[a][0]<d[b][0])
                    printf("(%d, %d) RIGHT\n",d[a][0],d[a][1]);
                else
                    printf("(%d, %d) LEFT\n",d[a][0],d[a][1]);
            }
        }
    }
    return 0;
}
void dfs(int u,int fa)
{
    int len=g[u].size();
    vis[u]=1;
    for(int i=0;i<len;i++)
    {
        if(vis[g[u][i]]==0&&g[u][i]!=fa)
        {
            dfs(g[u][i],u);
            vec.push_back(node(g[u][i],u));
        }
    }
}