Advertisement
Guest User

Untitled

a guest
Dec 29th, 2019
750
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.86 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC target("avx,avx2")
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. ostream& operator<<(ostream &out, string str) {
  7.     for(char c : str) out << c;
  8.     return out;
  9. }
  10.  
  11. template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
  12.     return out << "(" << p.first << ", " << p.second << ")";
  13. }
  14.  
  15. template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
  16.     out << "{";
  17.     for(auto it = a.begin(); it != a.end(); it = next(it))
  18.         out << (it != a.begin() ? ", " : "") << *it;
  19.     return out << "}";
  20. }
  21.  
  22. void dump() { cerr << "\n"; }
  23. template<class T, class... Ts> void dump(T a, Ts... x) {
  24.     cerr << a << ", ";
  25.     dump(x...);
  26. }
  27.  
  28. #ifdef DEBUG
  29. #  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
  30. #else
  31. #  define debug(...) false
  32. #endif
  33.  
  34. #define REP(i, n) for(int i = 0; i < n; i++)
  35. #define FOR(i, a, b) for(int i = a; i <= b; i++)
  36. #define ST first
  37. #define ND second
  38.  
  39. template<class T> int size(T && a) { return a.size(); }
  40.  
  41. using LL = long long;
  42. using PII = pair<int, int>;
  43.  
  44. mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
  45. int rd(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
  46.  
  47. int main() {
  48.     ios_base::sync_with_stdio(0);
  49.     cin.tie(0);
  50.  
  51.     int n;
  52.     cin >> n;
  53.     vector<int> x(n), y(n);
  54.     REP(i, n) cin >> x[i] >> y[i];
  55.  
  56.     vector<LL> w;
  57.     vector<vector<PII>> e;
  58.     map<LL, int> S;
  59.     map<LL, bool> used;
  60.  
  61.     REP(i, n) REP(j, n) {
  62.         LL _x = x[i] - x[j];
  63.         LL _y = y[i] - y[j];
  64.         LL d = _x * _x + _y * _y;
  65.         if(S.find(d) == S.end()) {
  66.             S[d] = size(e);
  67.             e.emplace_back();
  68.         }
  69.  
  70.         int id = S[d];
  71.         e[id].emplace_back(i, j);
  72.         w.emplace_back(d); 
  73.     }
  74.  
  75.     while(true) {
  76.         LL x = w[rd(0, size(w) - 1)];
  77.         while(used[x]) {
  78.             x = w[rd(0, size(w) - 1)];
  79.         }
  80.         used[x] = true;
  81.  
  82.         vector<vector<int>> graph(n);
  83.         int id = S[x];
  84.         for(PII p : e[id]) {
  85.             int i, j;
  86.             tie(i, j) = p;
  87.             graph[i].emplace_back(j);
  88.             graph[j].emplace_back(i);
  89.         }
  90.        
  91.         vector<int> col(n, -1);
  92.         bool good = true;
  93.         REP(i, n) {
  94.             if(col[i] == -1) {
  95.                 vector<int> Q = {i};
  96.                 col[i] = 0;
  97.  
  98.                 while(!Q.empty()) {
  99.                     int v = Q.back();
  100.                     Q.pop_back();
  101.  
  102.                     for(int u : graph[v]) {
  103.                         if(col[u] == -1) {
  104.                             col[u] = col[v] ^ 1;
  105.                             Q.emplace_back(u);
  106.                         }
  107.                         else if(col[u] == col[v]) {
  108.                             good = false;
  109.                             break;
  110.                         }
  111.                     }
  112.  
  113.                     if(!good) break;
  114.                 }
  115.             }
  116.  
  117.             if(!good) break;
  118.         }
  119.  
  120.         if(!good) continue;
  121.  
  122.         for(auto &v : e) {
  123.             int q = -1;
  124.             for(PII p : v) {
  125.                 int x = col[p.ST] ^ col[p.ND];
  126.                 if(q == -1) q = x;
  127.                 if(q != x) {
  128.                     good = false;
  129.                     break;
  130.                 }
  131.             }
  132.  
  133.             if(!good) break;
  134.         }
  135.  
  136.         if(!good) continue;
  137.  
  138.         int cnt = 0;
  139.         REP(i, n) if(col[i]) cnt++;
  140.         cout << cnt << "\n";
  141.         REP(i, n) if(col[i]) cout << i + 1 << " ";
  142.         cout << "\n";
  143.         return 0;
  144.     }
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement