Problem's Link

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
" :: "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;
}