Advertisement
Guest User

E innopolis

a guest
Nov 22nd, 2020
796
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.67 KB | None | 0 0
  1. //나는 가상 소녀들에게 큰 호감이 있습니다.
  2.  
  3. #include <iostream>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <stdio.h>
  7. #include <cstring>
  8. #include <string>
  9. #include <cstdlib>
  10. #include <vector>
  11. #include <bitset>
  12. #include <map>
  13. #include <chrono>
  14. #include <functional>
  15. #include <unordered_set>
  16. #include <unordered_map>
  17. #include <numeric>
  18. #include <queue>
  19. #include <ctime>
  20. #include <stack>
  21. #include <set>
  22. #include <list>
  23. #include <deque>
  24. #include <iomanip>
  25. #include <sstream>
  26. #include <fstream>
  27. #include <stdarg.h>
  28. #include <utility>
  29.  
  30. using namespace std;
  31.  
  32. #define pb push_back
  33. #define mp make_pair
  34. #define ll long long
  35. #define ull unisgned long long
  36. #define ld long double
  37. #define all(a) a.begin(), a.end()
  38. #define SORT(a) sort(all(a))
  39. #define pii pair<int, int>
  40. #define tii triple<int, int, int>
  41. #define e 1e-7
  42. #define PI acos(-1)
  43. #define sz(a) (int)(a.size())
  44. #define inf 1e17
  45. #define vi vector<int>
  46. #define F first
  47. #define S second
  48. #define rng(x) for(int _ = 0; _ < (x); _++)
  49. #define rngi(i, x) for(int i = 0; i < (x); i++)
  50. #define rngsi(s, i, x) for(int i = (s); i <(x); i++)
  51. #define int long long
  52. #define problem "a"
  53.  
  54. template<typename A, typename B, typename C>
  55. struct triple {
  56.     A X;
  57.     B Y;
  58.     C Z;
  59.     triple(A a = 0, B b = 0, C c = 0) :X(a), Y(b), Z(c) {}
  60. };
  61. template<typename A, typename B, typename C>
  62. triple<A, B, C> make_triple(A a = 0, B b = 0, C c = 0) {
  63.     return triple<A, B, C>(a, b, c);
  64. }
  65. template<typename A, typename B, typename C>
  66. bool operator<(const triple<A, B, C>& a, const triple<A, B, C>& b) {
  67.     if (a.X != b.X)
  68.         return a.X < b.X;
  69.     if (a.Y != b.Y)
  70.         return a.Y < b.Y;
  71.     return a.Z < b.Z;
  72. }
  73. template<typename T, typename SS>
  74. ostream& operator<<(ostream& ofs, const pair<T, SS>& p) {
  75.     ofs << "( " << p.F << " , " << p.S << " )";
  76.     return ofs;
  77. }
  78. template<typename T>
  79. void print(T a) {
  80.     for (auto i : a)
  81.         cout << i << ' ';
  82.     cout << '\n';
  83. }
  84. template<typename T>
  85. T max(T a, T b, T c) {
  86.     return max(a, max(b, c));
  87. }
  88. template<typename T>
  89. T min(T a, T b, T c) {
  90.     return min(a, min(b, c));
  91. }
  92. template<typename T, typename D>
  93. D min(T a) {
  94.     return *min_element(all(a));
  95. }
  96. template<typename T, typename D>
  97. D max(T a) {
  98.     return *max_element(all(a));
  99. }
  100. struct custom_hash {
  101.     static uint64_t splitmix64(uint64_t x) {
  102.         x += 0x9e3779b97f4a7c15;
  103.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  104.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  105.         return x ^ (x >> 31);
  106.     }
  107.  
  108.     size_t operator()(uint64_t x) const {
  109.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  110.         return splitmix64(x + FIXED_RANDOM);
  111.     }
  112. };
  113. void solve() {
  114.     int n; cin >> n;
  115.     vector<pii> a(n);
  116.     rngi(i, n) cin >> a[i].first >> a[i].second;
  117.     int ans = 4;
  118.     rng(2) {
  119.         vi xx, yy;
  120.         rngi(i, n) xx.push_back(a[i].first), yy.push_back(a[i].second);
  121.         SORT(xx); xx.erase(unique(all(xx)), xx.end());
  122.         SORT(yy); yy.erase(unique(all(yy)), yy.end());
  123.         vector<vi> mx(n), my(n);
  124.         vector<pii> b;
  125.         rngi(i, n) {
  126.             int x = a[i].first, y = a[i].second;
  127.             x = lower_bound(all(xx), x) - xx.begin();
  128.             y = lower_bound(all(yy), y) - yy.begin();
  129.             b.push_back({ x,y });
  130.             mx[x].push_back(y);
  131.         }
  132.         rngi(i, n) SORT(mx[i]), SORT(my[i]);
  133.         int lim = sqrt(n) + 2;
  134.         vector<pii> c;
  135.         rngi(i, n)
  136.             if (sz(mx[i]) < lim)for (auto v : mx[i]) c.push_back({ i, v });
  137.         for (auto p : c) my[p.second].push_back(p.first);
  138.         rngi(i, n) SORT(my[i]);
  139.         vi cnt(n);
  140.         rngi(i, n) {
  141.             for (auto x : my[i]) for (auto d : mx[x]) if (d > i) {
  142.                 cnt[d]++; if (cnt[d] == 2)return void(cout << "0\n");
  143.             }
  144.             for (auto x : my[i]) for (auto d : mx[x]) if (d > i) {
  145.                 cnt[d]--;
  146.             }
  147.         }
  148.         vector<vi> ptr(n);
  149.         cnt.assign(n, 0);
  150.         rngi(i, n) if (sz(mx[i]) >= lim) for (auto d : mx[i]) ptr[d].push_back(i);
  151.         rngi(i, n) {
  152.             if (sz(mx[i]) < lim) for (auto d : mx[i]) for (auto t : ptr[d]) { cnt[t]++;  if (cnt[d] == 2)return void(cout << "0\n"); }
  153.  
  154.             if (sz(mx[i]) < lim) for (auto d : mx[i]) for (auto t : ptr[d]) { cnt[t]--; }
  155.         }
  156.         rngi(i, n) swap(a[i].first, a[i].second);
  157.     }
  158.  
  159.     vi xx, yy;
  160.     rngi(i, n) xx.push_back(a[i].first), yy.push_back(a[i].second);
  161.     SORT(xx); xx.erase(unique(all(xx)), xx.end());
  162.     SORT(yy); yy.erase(unique(all(yy)), yy.end());
  163.     vi cx(n), cy(n);
  164.     vector<pii> b;
  165.     vector< vi > mx(n), my(n);
  166.     rngi(i, n) {
  167.         int x = a[i].first, y = a[i].second;
  168.         x = lower_bound(all(xx), x) - xx.begin();
  169.         y = lower_bound(all(yy), y) - yy.begin();
  170.         b.push_back({ x,y });
  171.         cx[x]++; cy[y]++;
  172.         mx[x].push_back(y);
  173.         my[y].push_back(x);
  174.     }
  175.     vi d(n);
  176.     rngi(i, n) if (cx[i] > 1)  for (auto v : mx[i]) {
  177.         d[v]++; if (d[v] == 2) return void(cout << "1\n");
  178.     }
  179.     d.assign(n, 0);
  180.     rngi(i, n) if (cy[i] > 1)  for (auto v : my[i]) {
  181.         d[v]++; if (d[v] == 2) return void(cout << "1\n");
  182.     }
  183.     int aa = 0;
  184.     rngi(i, n) if (cx[i] > 1) aa++;
  185.     if(aa > 1)return void(cout << "2\n");
  186.     aa = 0;
  187.  
  188.     rngi(i, n) if (cy[i] > 1) aa++;
  189.     if (aa > 1)return void(cout << "2\n");
  190.     rngi(i, n) if (cx[b[i].first] > 1 && cy[b[i].second] > 1)return void(cout << "2\n");
  191.    
  192.  
  193.     rngi(i, n) if((cx[b[i].first] > 1 || cy[b[i].second] > 1) && (cx[b[i].first] != n && cy[b[i].second] != n))return void(cout << "3\n");
  194.     cout << 4 << '\n';
  195. };
  196. void working() {
  197.     int n; cin >> n;
  198.     vector<pii> a(n);
  199.     rngi(i, n) cin >> a[i].first >> a[i].second;
  200.     int ans = 4;
  201.     rng(2) {
  202.         vi xx, yy;
  203.         rngi(i, n) xx.push_back(a[i].first), yy.push_back(a[i].second);
  204.         SORT(xx); xx.erase(unique(all(xx)), xx.end());
  205.         SORT(yy); yy.erase(unique(all(yy)), yy.end());
  206.         vector<vector<char> > have(n, vector<char>(n));
  207.         vector<pii> b;
  208.         rngi(i, n) {
  209.             int x = a[i].first, y = a[i].second;
  210.             x = lower_bound(all(xx), x) - xx.begin();
  211.             y = lower_bound(all(yy), y) - yy.begin();
  212.             b.push_back({ x,y });
  213.             have[x][y] = 1;
  214.         }
  215.         vi cx(n), cy(n);
  216.         rngi(i, n) cx[b[i].first]++;
  217.         rngi(i, n) cy[b[i].second]++;
  218.  
  219.         rngi(i, n) rngi(j, n) {
  220.             if (!ans)break;
  221.             int x1 = b[i].first, y1 = b[i].second, x2 = b[j].first, y2 = b[j].second;
  222.             if (x1 < x2 && y1 < y2) {
  223.                 int d = 4;
  224.                 if (have[x1][y2]) d -= 2;
  225.                 else if (cx[x1] > 1 || cy[y2] > 1) d--;
  226.  
  227.                 if (have[x2][y1]) d -= 2;
  228.                 else if (cx[x2] > 1 || cy[y1] > 1) d--;
  229.                 ans = min(ans, d);
  230.             }
  231.         }
  232.         rngi(i, n) a[i].second = -a[i].second;
  233.     }
  234.     cout << ans << '\n';
  235. }
  236. signed main()
  237. {
  238.     if (0) {
  239.         freopen("1.in", "r", stdin);
  240.         freopen("bad.out", "w", stdout);
  241.     }
  242.     srand(time(NULL));
  243.     cin.tie(0);
  244.     cout.tie(0);
  245.     ios_base::sync_with_stdio(false);
  246.     if (0) {
  247.         cout << "50\n";
  248.         rng(50) {
  249.             int n = 1 + rand() % 10;
  250.             cout << n << '\n';
  251.             rng(n) {
  252.                 int x = rand() % 10, y = rand() % 10;
  253.                 cout << x << ' ' << y << '\n';
  254.             }
  255.         }
  256.         return 0;
  257.     }
  258.     int t = 1; cin >> t;
  259.     rng(t) solve();
  260. }
  261.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement