Fzu oj2194星系碰撞（排序+并查集+路径压缩）

Problem 2194 星系碰撞

Accept: 14 Submit: 48
Time Limit: 30000 mSec Memory Limit : 327680 KB

Problem Description

据预测，大约在100亿年后，狮子座星系将与银河系发生碰撞，两个星系的碰撞将会合并两个星系，但是没有2个星球会相撞。现在某科学家得到两个星系合并后的结果，一些二维平面上的点，但是不知道那些星球属于银河系，已知如果两个星球属于同一个星系，那么他们之间的距离大于5光年，这边的距离指的是欧几里得距离，即（x1,y1）与（x2,y2）的距离为sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))。现在想请你帮忙把合并后的结果分成2个集合，一个属于银河系，一个属于狮子座星系，由于集合划分的方案可能有多种，现在想知道最多有多少个星球可能属于银河系。（可以所有星球都属于银河系）

例如:如下图有6个点，你可以有以下4中划分{{1, 2, 4, 5}, {3, 6}}; {{1, 2, 3, 4}, {5, 6}}; {{1, 4,5}, {2, 3, 6}}; {{1, 3, 4}, {2, 5, 6}} ，那么可以采用第一种划分{1,2,4,5} 都属于银河系，答案为4.

Fzu oj2194星系碰撞（排序+并查集+路径压缩）-LMLPHP

Input

包含多组数据每组数据输入第一行一个整数N 表示星球个数（1<=N<=50000）,接下去N 行每行2个整数 x和y 表示星球的坐标（1<=x,y<=500000）,没有重合的点。

Output

输出一行一个整数表示最多有多少个星球属于银河系。如果没办法进行划分那么输出-1。

Sample Input

6
1 3
9 1
11 7
5 7
13 5
4 4

Sample Output

分析：把所有的行星按照x坐标从小到大排序，然后枚举两点（加剪枝）距离，若距离小于等于5，若这两个点不在一个集合当中，则加入一个集合，并且这两个相连的点染为不同的颜色，若这两个点在一个集合当中，则判定矛盾，因为再改集合中至少有三个点，他们两两之间的距离都小于等于5，就是说无论怎样分配他们都无法满足题目要求，如果不存在矛盾的情况，则计算出每个集合当中被染成两种颜色的个数max1和max2，最后把所有集合当中的较大者加起来即：sum+=max(max1[k]+max2[k])(k属于不同的集合)

程序;

#include"stdio.h"

#include"string.h"

#include"math.h"

#include"iostream"

#include"queue"

#include"algorithm"

#include"stack"

#include"map"

#include"string"

#define M 50009

#define inf 0x3f3f3f3f

#define eps 1e-9

#define LL __int64

using namespace std;

struct node

{

    int x,y;

}p[M];

int cmp(node a,node b)

{

    return a.x<b.x;

}

LL dist(node a,node b)

{

    return (LL)(a.x-b.x)*(a.x-b.x)+(LL)(a.y-b.y)*(a.y-b.y);

}

int f[M],max1[M],max2[M],sum[M];

int finde(int x)

{

    if(x!=f[x])

    {

        int t=f[x];

        f[x]=finde(f[x]);

        sum[x]=(sum[x]+sum[t])%2;

    }

    return f[x];

}

int ok(int n)

{

    for(int i=0;i<n;i++)

    {

        f[i]=i;

        sum[i]=0;

    }

    for(int i=0;i<n;i++)

    {

        for(int j=i+1;j<n;j++)

        {

            if(p[j].x-p[i].x>5)break;

            if(dist(p[i],p[j])<=25LL)

            {

                int x=finde(i);

                int y=finde(j);

                if(x!=y)

                {

                    f[y]=x;

                    sum[y]=(sum[x]+sum[i]+1-sum[j])%2;

                }

                else

                {

                    if(sum[x]==sum[y])

                    return -1;

                }

            }

        }

    }

    memset(max1,0,sizeof(max1));

    memset(max2,0,sizeof(max2));

    for(int i=0;i<n;i++)

    {

        int y=finde(i);

        f[i]=y;

        if(sum[i]==0)

            max1[y]++;

        else

            max2[y]++;

    }

    int ans=0;

    for(int i=0;i<n;i++)

    {

        if(f[i]==i)

        {

            ans+=max(max1[i],max2[i]);

        }

    }

    return ans;

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        for(int i=0;i<n;i++)

        {

            scanf("%d%d",&p[i].x,&p[i].y);

        }

        sort(p,p+n,cmp);

        printf("%d\n",ok(n));

    }

    return 0;

}

星系