Galaxy collision 

---

 

Mean: 

给定二维坐标平面内的n个整数点，让你把这n个点划分为两个集合，同一集合内的所有点必须两两距离大于5，求这两个集合的元素个数之差最大是多少。

analyse:

由题意可知：同一个圆内包含的点肯定不能和这个圆心点在同一集合，且题目保证了一定有答案。

而且都是整数点，每个圆包含的点不会超过100个，那么就可以枚举园内的每一个"虚点"看题目中有没有出现这个点，然后对所有点DFS，ans1统计点多的集合，ans2统计点少的集合，最后相减即得答案。

Time complexity: O(N)

 

Source code: 

/*

* this code is made by crazyacking

* Verdict: Accepted

* Submission Date: 2015-10-06-23.02

* Time: 0MS

* Memory: 137KB

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#define max(a,b) (a>b?a:b)

using

namespace

std;

typedef

long

long(

LL);

typedef

unsigned

long

long(

ULL);

const

double

eps(

1e-8);

struct

Point

{

     

int

x

,

y;

     

Point()

{}

     

Point(

int

x

,

int

y)

     

{

           

this

->

x

=

x;

           

this

->

y

=

y;

     

}

     

bool

operator

<(

Point

one)

const

     

{

           

if(

x

!=

one

.

x)

                 

return

x

<

one

.

x;

           

return

y

<

one

.

y;

     

}

};

vector

<

Point

>

bx;

int

dis2(

Point

one

,

Point

two)

{

     

return (

one

.

x

-

two

.

x)

*(

one

.

x

-

two

.

x)

+(

one

.

y

-

two

.

y)

*(

one

.

y

-

two

.

y);

}

void

create()

{

     

for(

int

i

=-

5;

i

<=

5;

i

++)

           

for(

int

j

=-

5;

j

<=

5;

j

++)

                 

if(

dis2(

Point(

i

,

j

),

Point(

0

,

0))

<=

25)

                       

bx

.

push_back(

Point(

i

,

j));

}

map

<

Point

,

int

>

mp;

Point

cnt;

int

sum;

void

dfs(

Point

v)

{

     

sum

++;

     

if(

sum

>=

100000)

           

exit(

0);

     

int n

=

bx

.

size

(),

no

=

mp

[

v

];

     

map

<

Point

,

int

>::

iterator

it;

     

for(

int

i

=

0;

i

<n;

i

++)

     

{

           

Point

t

=

Point(

v

.

x

+

bx

[

i

].

x

,

v

.

y

+

bx

[

i

].

y);

           

it

=

mp

.

find(

t);

           

if(

it

!=

mp

.

end()

&&

it

->

second

==

0)

           

{

                 

if(

no

==

1)

                 

{

                       

it

->

second

=

2;

                       

cnt

.

y

++;

                 

}

                 

else

                 

{

                       

it

->

second

=

1;

                       

cnt

.

x

++;

                 

}

                 

dfs(

t);

           

}

     

}

}

int

main()

{

     

int

size

=

256

<<

20;

// 256MB

     

char

*p

= (

char

*)

malloc(

size)

+

size;

     

__asm__(

"movl %0, %%esp

\n

"

::

"r"(p));

     

create();

     

int n;

     

scanf(

"%d"

,

&n);

     

while(n

--)

     

{

           

Point

t;

           

scanf(

"%d%d"

,

&

t

.

x

,

&

t

.

y);

           

mp

[

t

]

=

0;

     

}

     

map

<

Point

,

int

>::

iterator

it;

     

int

ans

=

0;

     

for(

it

=

mp

.

begin();

it

!=

mp

.

end();

it

++)

     

{

           

if(

it

->

second

==

0)

           

{

                 

it

->

second

=

1;

                 

cnt

.

x

=

1;

                 

cnt

.

y

=

0;

                 

dfs(

it

->

first);

                 

if(

cnt

.

x

>

cnt

.

y)

                       

swap(

cnt

.

x

,

cnt

.

y);

                 

ans

+=

cnt

.

x;

           

}

     

}

     

cout

<<

ans

<<

endl;

     

return

0;

}