Advertisement
Guest User

Untitled

a guest
Dec 29th, 2019
389
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <algorithm>
  7. #include <string>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <iomanip>
  11. #include <fstream>
  12. #include <cassert>
  13. #include <cstring>
  14. #include <unordered_set>
  15. #include <unordered_map>
  16. #include <numeric>
  17. #include <ctime>
  18. #include <bitset>
  19. #include <complex>
  20. #include <random>
  21.  
  22. using namespace std;
  23.  
  24. #define int long long
  25.  
  26. int get(int x) {
  27.     return ((x % 2) + 2) % 2;
  28. }
  29.  
  30. int n;
  31. vector<pair<int, int>> a;
  32. vector<int> d[2][2];
  33.  
  34. void filld() {
  35.     for (int i = 0; i < 2; i++) {
  36.         for (int j = 0; j < 2; j++) {
  37.             d[i][j].clear();
  38.         }
  39.     }
  40.     for (int i = 0; i < n; i++) {
  41.         d[get(a[i].first)][get(a[i].second)].push_back(i);
  42.     }
  43. }
  44.  
  45. int lol(int i, int j) {
  46.     int df = a[i].first - a[j].first;
  47.     int ds = a[i].second - a[j].second;
  48.     return df * df + ds * ds;
  49. }
  50.  
  51. void out(vector<int> v) {
  52.     sort(v.begin(), v.end());
  53.     v.resize(unique(v.begin(), v.end()) - v.begin());
  54.     if ((int)v.size() == n) {
  55.         return;
  56.     }
  57.     if (v.empty()) {
  58.         return;
  59.     }
  60.     vector<int> gr(n, 0);
  61.     for (auto t : v) {
  62.         gr[t] = 1;
  63.     }
  64.     set<int> s1;
  65.     set<int> s2;
  66.     for (int i = 0; i < n; i++) {
  67.         for (int j = i + 1; j < n; j++) {
  68.             if (gr[i] == gr[j]) {
  69.                 s1.insert(lol(i, j));
  70.             } else {
  71.                 s2.insert(lol(i, j));
  72.             }
  73.         }
  74.     }
  75.     int ok = 1;
  76.     for (auto t : s2) {
  77.         if (s1.count(t)) {
  78.             ok = 0;
  79.         }
  80.     }
  81.     for (auto t : s1) {
  82.         if (s2.count(t)) {
  83.             ok = 0;
  84.         }
  85.     }
  86.     if (ok) {
  87.         cout << v.size() << endl;
  88.         for (auto t : v) {
  89.             cout << t + 1 << ' ';
  90.         }
  91.         cout << endl;
  92.         exit(0);
  93.     }
  94. }
  95.  
  96. void rec() {
  97.     filld();
  98.     {
  99.         vector<int> v;
  100.         for (auto t : d[0][0]) v.push_back(t);
  101.         for (auto t : d[1][1]) v.push_back(t);
  102.         out(v);
  103.     }
  104.     out(d[0][0]);
  105.     out(d[0][1]);
  106.     for (int i = 0; i < n; i++) {
  107.         a[i].first -= abs(a[i].first % 2);
  108.         a[i].second -= abs(a[i].second % 2);
  109.         a[i].first /= 2;
  110.         a[i].second /= 2;
  111.     }
  112.     rec();
  113. }
  114.  
  115. signed main() {
  116.     ios_base::sync_with_stdio(false);
  117.     cin.tie(0);
  118.    
  119.     cin >> n;
  120.     a.resize(n);
  121.     for (auto &t : a) {
  122.         cin >> t.first >> t.second;
  123.     }
  124.     vector<pair<int, int>> ta = a;
  125.     sort(ta.begin(), ta.end());
  126.     ta.resize(unique(ta.begin(), ta.end()) - ta.begin());
  127.     assert((int)ta.size() == n);
  128.     rec();
  129.     assert(false);
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement