#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; struct Point{ int x, y; int id; }; struct Node{ Point p; Node* left; Node* right; }; typedef vector VP; bool LessX(const Point& left, const Point& right){ if (left.x == right.x) return(left.y < right.y); else return(left.x < right.x); } bool LessY(const Point& left, const Point& right){ if (left.y == right.y) return(left.x < right.x); else return(left.y < right.y); } vector exist(100001, false); inline int dist(Point& a, Point &b){ return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y); } bool rect_search(Node* root, Point st, Point ed,Point t, bool odd){ if (root == NULL)return false; //if ((st.x <= root->p.x&&root->p.x <= ed.x) && (st.y <= root->p.y&&root->p.y <= ed.y))implements.push_back(root->p); if (exist[root->p.id] && dist(root->p, t) < 400)return true; if (odd){ if (ed.y < root->p.y){ //領域が分割線よりも下側 if (rect_search(root->left, st, ed, t, odd ^ 1))return true; } else if (st.y > root->p.y){ //領域が分割線よりも上側 if(rect_search(root->right, st, ed, t,odd ^ 1))return true; } else{ //領域が分割線にまたがる Point mid_l = { ed.x, root->p.y };//分割線の左端 Point mid_r = { st.x, root->p.y };//分割線の右端 if(rect_search(root->left, st, mid_l, t,odd ^ 1))return true; if(rect_search(root->right, mid_r, ed, t, odd ^ 1))return true; } } else{ if (ed.x < root->p.x){ //領域が分割線よりも左側 if(rect_search(root->left, st, ed, t,odd ^ 1))return true; } else if (st.x > root->p.x){ //領域が分割線よりも右側 if(rect_search(root->right, st, ed, t,odd ^ 1))return true; } else{ //領域が分割線にまたがる Point mid_l = { root->p.x, ed.y };//分割線の上端 Point mid_r = { root->p.x, st.y };//分割線の下端 if(rect_search(root->left, st, mid_l, t,odd ^ 1))return true; if(rect_search(root->right, mid_r, ed, t, odd ^ 1))return true; } } return false; } Node* make_Tree(VP::iterator main_s, VP::iterator main_e, VP::iterator sub_s, VP::iterator sub_e, int size, bool odd){ if (size <= 0){ return(NULL); } Node* n = (Node*)calloc(1, sizeof(Node)); VP::iterator mid = main_s + size / 2; n->p = *mid; if (size == 1){ n->left = NULL; n->right = NULL; } else{ VP l, r; l.reserve(size / 2); r.reserve(size - size / 2); for (VP::iterator it = sub_s; it != sub_e; ++it) //深さが奇数のノードのとき,yで分割 if ((odd&&LessY(*it, *mid)) || ((!odd) && LessX(*it, *mid))) l.push_back(*it); else if ((it->x != mid->x) || (it->y != mid->y)) r.push_back(*it); n->left = make_Tree(l.begin(), l.end(), main_s, mid, size / 2, odd ^ 1); n->right = make_Tree(r.begin(), r.end(), mid + 1, main_e, size - size / 2 - 1, odd ^ 1); } return n; } void free_Tree(Node* root){ //printf("Node(%d,%d)\n", root->p.x, root->p.y); if (root->left != NULL) free_Tree(root->left); if (root->right != NULL) free_Tree(root->right); free(root); return; } bool operator<(const Point&left, const Point&right){ if (left.x == right.x) return(left.y < right.y); else return(left.x < right.x); } #define all(_b) (_b).begin(),(_b).end() int main(void){ int n,res=0; cin >> n; VP input(n); set memo; for (int i = 0; i < n; i++){ cin >> input[i].x >> input[i].y; input[i].id = i; if (memo.count(input[i]) == 1){ i--, n--; } } input.resize(n); VP x=input,y = input; sort(all(x), LessX); sort(all(y), LessY); Node *root = make_Tree(all(x), all(y), n,false); for (int i = 0; i < n; i++){ Point st, ed; st.x = input[i].x - 20; st.y = input[i].y - 20; ed.x = input[i].x + 20; ed.y = input[i].y + 20; if (rect_search(root, st, ed, input[i], false)==false){ exist[i] = true; res++; } } free_Tree(root); cout << res << endl; return(0); }