Advertisement
Guest User

Untitled

a guest
Nov 13th, 2014
346
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 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.                 // cout << "1" << " ";
  24.                 dist.push_back(point(x,y));
  25.             }
  26.             // else {
  27.             //  cout << "0" << " ";
  28.             // }
  29.         }
  30.         cout << endl;
  31.     }
  32.     int n,x,y;
  33.     while(scanf("%d",&n)==1){
  34.         m.clear();
  35.         for(int i = 1; i <= n; i++){
  36.             scanf("%d%d",&x,&y);
  37.             v[i] = point(x,y);
  38.             m[point(x,y)] = i;
  39.             adj[i].clear();
  40.         }
  41.         for (int i = 1; i <= n; i++){
  42.             x = v[i].first;
  43.             y = v[i].second;
  44.             for(int j = 0 ; j < dist.size() ; j++){
  45.                 int xx = x + dist[j].first;
  46.                 int yy = y + dist[j].second;
  47.                 int mapped = m[point(xx,yy)];
  48.                 if(mapped){
  49.                     adj[i].push_back(mapped);
  50.                     adj[mapped].push_back(i);
  51.                 }
  52.             }
  53.         }
  54.         memset(vis,0,sizeof vis);
  55.         int ans = 0;
  56.         for(int i = 1 ; i <= n; i++){
  57.             if(!vis[i]){
  58.                 int one = 1;
  59.                 int two = 0;
  60.                 queue<int> q;
  61.                 q.push(i);
  62.                 vis[i] = 1;
  63.                 while(!q.empty()){
  64.                     int from = q.front();q.pop();
  65.                     for(int j = 0 ; j < adj[from].size() ; j++){
  66.                         int to = adj[from][j];
  67.                         if(!vis[to]){
  68.                             q.push(to);
  69.                             vis[to] = (vis[from] == 1) ? 2 : 1;
  70.                             one += (vis[to] == 1);
  71.                             two += (vis[to] == 2);
  72.                         }
  73.                     }
  74.                 }
  75.                 ans += min(one,two);
  76.             }
  77.         }
  78.         printf("%d\n",ans);
  79.     }
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement