Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef pair<int,int> point;
- const int MAXN = 50010;
- map<point,int> m;
- point v[MAXN];
- int vis[MAXN];
- vector<int> adj[MAXN];
- bool euclidean_dist(int x,int y){
- return (hypot(x,y) <= 5.0);
- }
- int main(){
- vector<point> dist;
- for(int x = -5 ; x <= 5 ; x++){
- for(int y = -5 ; y <= 5 ; y++){
- if(euclidean_dist(x,y) && (x|y) ){
- // cout << "1" << " ";
- dist.push_back(point(x,y));
- }
- // else {
- // cout << "0" << " ";
- // }
- }
- cout << endl;
- }
- int n,x,y;
- while(scanf("%d",&n)==1){
- m.clear();
- for(int i = 1; i <= n; i++){
- scanf("%d%d",&x,&y);
- v[i] = point(x,y);
- m[point(x,y)] = i;
- adj[i].clear();
- }
- for (int i = 1; i <= n; i++){
- x = v[i].first;
- y = v[i].second;
- for(int j = 0 ; j < dist.size() ; j++){
- int xx = x + dist[j].first;
- int yy = y + dist[j].second;
- int mapped = m[point(xx,yy)];
- if(mapped){
- adj[i].push_back(mapped);
- adj[mapped].push_back(i);
- }
- }
- }
- memset(vis,0,sizeof vis);
- int ans = 0;
- for(int i = 1 ; i <= n; i++){
- if(!vis[i]){
- int one = 1;
- int two = 0;
- queue<int> q;
- q.push(i);
- vis[i] = 1;
- while(!q.empty()){
- int from = q.front();q.pop();
- for(int j = 0 ; j < adj[from].size() ; j++){
- int to = adj[from][j];
- if(!vis[to]){
- q.push(to);
- vis[to] = (vis[from] == 1) ? 2 : 1;
- one += (vis[to] == 1);
- two += (vis[to] == 2);
- }
- }
- }
- ans += min(one,two);
- }
- }
- printf("%d\n",ans);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement