fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Point {
  5.     static long long Radius;
  6.     int x, y;
  7.     bool checked;
  8.     Point() : x(-1), y(-1), checked(false) {}
  9.     Point(int u, int v) : x(u), y(v), checked(false) {}
  10.  
  11.     friend ostream &operator << (ostream &os, const Point &o) {
  12.         return os << "(" << o.x << ", " << o.y << ")";
  13.     }
  14.  
  15.     friend istream &operator >> (istream &is, Point &o) {
  16.         return is >> o.x >> o.y;
  17.     }
  18.  
  19.     bool operator < (const Point &o) const {
  20.         return x != o.x ? x < o.x : y < o.y;
  21.     }
  22.  
  23.     friend long long dis(const Point &a, const Point &b) {
  24.         return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
  25.     }
  26.  
  27.     friend bool connected(const Point &a, const Point &b) {
  28.         return dis(a, b) <= 1LL * Point::Radius * Point::Radius;
  29.     }
  30. }; 
  31.  
  32. long long Point::Radius = 0;
  33.  
  34. struct DSU {
  35.     int n;
  36.     vector<int> e;
  37.     vector<bool> c;
  38.     DSU(int n = 0) : n(n), e(n + 1, -1), c(n + 1, 0) {}
  39.  
  40.     int fp(int u) {
  41.         return e[u] < 0 ? u : e[u] = fp(e[u]);
  42.     }
  43.  
  44.     bool unon(int u, int v) {
  45.         u = fp(u);
  46.         v = fp(v);
  47.         if(u == v) return false;
  48.         if(e[u] > e[v]) swap(u, v);
  49.         c[u] = c[u] | c[v];
  50.         e[u] += e[v];
  51.         e[v] = u;
  52.         return true;
  53.     }
  54. };
  55.  
  56. const int MX = 100005;
  57. int n, r;
  58. int d[MX];
  59. Point point[MX];
  60. vector<int> G[MX];
  61. int CNT = 0;
  62. void addEdge(int u, int v) {
  63.     G[u].push_back(v);
  64. 	G[v].push_back(u);
  65. }
  66.  
  67. void buildGraph(bool ord) {
  68.     vector<int> orderId(n);
  69.     iota(orderId.begin(), orderId.end(), 1);
  70.     sort(orderId.begin(), orderId.end(),
  71.     ord ? [](const int &i, const int &j) -> bool {
  72.         return point[i] < point[j];
  73.     } : [](const int &i, const int &j) -> bool {
  74.         return point[j] < point[i];
  75.     });
  76.  
  77.     set<pair<int, int>> wl;
  78.     for(size_t x = 0, y = 0, i; x < orderId.size(); ++x) {
  79.         i = orderId[x];
  80.         while(y < x && abs(point[orderId[y]].x - point[i].x) > Point::Radius) {
  81.             int j = orderId[y];
  82.             wl.erase({point[j].y, j});
  83.             ++y;
  84.         }
  85.  
  86.         // proceed here
  87.         auto itr = wl.lower_bound({point[i].y - Point::Radius, -1});
  88.         vector<set<pair<int, int>>::iterator>connect;
  89.         while(itr != wl.end() && itr->first <= point[i].y + Point::Radius) {
  90.             if(connected(point[i], point[itr->second])) {
  91.                 connect.push_back(itr);
  92.                 addEdge(i, itr->second);
  93.             }
  94.             ++itr;
  95.         }
  96.  
  97.         if(connect.size() > 3) {
  98.             for(auto itr: connect) {
  99.                 int i = itr->second;
  100.                 point[i].checked = true;
  101.                 wl.erase(itr);
  102.             }
  103.         }
  104.  
  105.         wl.insert({point[i].y, i});
  106.     }
  107. }
  108.  
  109. void dfs(int u) {
  110.     for(int v: G[u]) {
  111.         if(!d[v]) d[v] = 3 - d[u], dfs(v);
  112.         else if(d[v] == d[u]) point[u].checked = true;
  113.     }
  114. }
  115.  
  116. void verify() {
  117.     DSU dsu(n);
  118.     for(int i = 1; i <= n; ++i) if(!d[i]) d[i] = 1, dfs(i);
  119.     for(int i = 1; i <= n; ++i) if(point[i].checked) dsu.c[i] = true;
  120.     for(int i = 1; i <= n; ++i) for(int j: G[i]) dsu.unon(i, j);
  121.     for(int i = 1; i <= n; ++i) if(dsu.c[dsu.fp(i)] == true) point[i].checked = true;
  122. }
  123.  
  124. int main() {
  125.     ios_base::sync_with_stdio(false);
  126.     cin.tie(0);
  127.  
  128.     cin >> n >> Point::Radius;
  129.     for(int i = 1; i <= n; ++i) cin >> point[i];
  130.  
  131.     buildGraph(true);
  132.     buildGraph(false);
  133.     verify();
  134.  
  135.     for(int i = 1; i <= n; ++i) cout << point[i].checked;
  136.  
  137.     return 0;
  138. }
  139.  
  140. /*
  141.  
  142. 6 5
  143. 4 1
  144. 4 4
  145. 1 5
  146. 5 9
  147. 9 6
  148. 10 2
  149.  
  150. */
Success #stdin #stdout 0.01s 6984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aH1seJ
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!