Guest User

Untitled

a guest
Nov 14th, 2014
493
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.84 KB | None | 0 0
  1. #include <bits/stdc++.h>      
  2.  
  3. using namespace std;
  4.  
  5. typedef pair<int,int> point;
  6.  
  7. const int MAXN = 50010;
  8.  
  9. map<point,int> m;
  10. point v[MAXN];
  11. int vis[MAXN];
  12. vector<int> adj[MAXN];
  13.  
  14. bool euclidean_dist(int x,int y){
  15.         return (hypot(x,y) <= 5.0);
  16. }
  17.  
  18. int main(){
  19.         vector<point> dist;
  20.         for(int x = -5 ; x <= 5 ; x++){
  21.                 for(int y = -5 ; y <= 5 ; y++){
  22.                         if(euclidean_dist(x,y) && (x|y) ){
  23.                                 dist.push_back(point(x,y));
  24.                         }
  25.                 }
  26.         }
  27.         int n,x,y;
  28.         while(scanf("%d",&n)==1){
  29.                 m.clear();
  30.                 for(int i = 1; i <= n; i++){
  31.                         scanf("%d%d",&x,&y);
  32.                         v[i] = point(x,y);
  33.                         m[point(x,y)] = i;
  34.                         adj[i].clear();
  35.                 }
  36.                 for (int i = 1; i <= n; i++){
  37.                         x = v[i].first;
  38.                         y = v[i].second;
  39.                         for(int j = 0 ; j < dist.size() ; j++){
  40.                                 int xx = x + dist[j].first;
  41.                                 int yy = y + dist[j].second;
  42.                                 if(m.count(point(xx,yy))){
  43.                                     int mapped = m[point(xx,yy)];
  44.                                     adj[i].push_back(mapped);
  45.                                     adj[mapped].push_back(i);
  46.                                 }
  47.                         }
  48.                 }
  49.                 memset(vis,0,sizeof vis);
  50.                 int ans = 0;
  51.                 for(int i = 1 ; i <= n; i++){
  52.                         if(!vis[i]){
  53.                                 int one = 1;
  54.                                 int two = 0;
  55.                                 queue<int> q;
  56.                                 q.push(i);
  57.                                 vis[i] = 1;
  58.                                 while(!q.empty()){
  59.                                         int from = q.front();q.pop();
  60.                                         for(int j = 0 ; j < adj[from].size() ; j++){
  61.                                                 int to = adj[from][j];
  62.                                                 if(!vis[to]){
  63.                                                         q.push(to);
  64.                                                         vis[to] = (vis[from] == 1) ? 2 : 1;
  65.                                                         one += (vis[to] == 1);
  66.                                                         two += (vis[to] == 2);
  67.                                                 }
  68.                                         }
  69.                                 }
  70.                                 ans += min(one,two);
  71.                         }
  72.                 }
  73.                 printf("%d\n",ans);
  74.         }
  75.         return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment