fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define llong long long 
  5. #define len(x) ((int)x.size())
  6. #define rep(i,n) for (int i = -1; ++ i < n; )
  7. #define rep1(i,n) for (int i = 0; i ++ < n; )
  8. #ifdef testing
  9. mt19937 rng(177013);
  10. #else
  11. mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
  12. #endif
  13. #define rand() (int)(rng() >> 1)
  14. #define CONCAT_(x, y) x##y/*{{{*/
  15. #define CONCAT(x, y) CONCAT_(x, y)
  16. #define SPEC(name) CONCAT(name, __LINE__)
  17. #ifdef LOCAL_DEBUG   
  18. int __db_level = 0;
  19. #define clog cerr << string(__db_level * 2, ' ')
  20. struct debug_block {
  21.     string msg;
  22.     debug_block(const string& s): msg(s) { clog << "{ " << msg << endl; ++__db_level; }
  23.     ~debug_block() { --__db_level; clog << "} " << msg << endl; }
  24. };
  25. #define DB(args...) stringstream SPEC(ss); SPEC(ss)<< args; debug_block SPEC(dbbl)(SPEC(ss).str())
  26. #else
  27. #define clog if (0) cerr
  28. #define DB(...)
  29. #endif
  30. #define db(val) "[" #val " = " << val << "]; "
  31. template<class U, class V> ostream& operator<<(ostream& out, const pair<U, V>& p) {
  32.     return out << "(" << p.first << ", " << p.second << ")";
  33. }
  34. template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
  35.     if constexpr(i == tuple_size<T>::value) return out << ")";
  36.     else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup);
  37. }
  38. template<class ...U>
  39. ostream& operator<<(ostream& out, const tuple<U...>& tup) { return print_tuple_utils<0, tuple<U...>>(out, tup); }
  40. template<class, typename = void> struct has_const_iterator : false_type {};
  41. template<class T> struct has_const_iterator<T, void_t<typename T::const_iterator>> : true_type {};
  42. template<class T>
  43. typename enable_if<has_const_iterator<T>::value && !is_same<T, string>::value, ostream&>::type
  44. operator<<(ostream& out, const T& container) { 
  45.     auto beg = container.begin(), end = container.end();
  46.     out << "(" << container.size() << ") {";
  47.     if (beg != end) out << *(beg++);
  48.     while (beg != end) out << ", " << *(beg++);
  49.     return out << "}";
  50. }
  51. #define ptrtype(x) typename iterator_traits<x>::value_type
  52. template<class u> vector<ptrtype(u)> $v(u a, u b) { return vector<ptrtype(u)>(a, b); }/*}}}*/
  53. // ACTUAL SOLUTION START HERE ////////////////////////////////////////////////////////////////
  54.  
  55. int getnum() {
  56.     int ch;
  57.     while (!isdigit(ch = getchar()) and ch != '-') {
  58.         if (ch == -1) return 0;
  59.     }
  60.     int sign = ch == '-' ? -1 : 1;
  61.     int ans = ch == '-' ? 0 : ch - '0';
  62.     while (isdigit(ch = getchar())) ans = ans * 10 + ch - '0';
  63.     // clog << ans << endl; 
  64.     return ans * sign;
  65. }
  66.  
  67. struct Point {
  68.     int x, y;
  69.     Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
  70.     friend ostream& operator<<(ostream& out, const Point& u) {
  71.         return out << "(" << u.x << ", " << u.y << ")";
  72.     }
  73. };
  74.  
  75. struct PointI {
  76.     int x, y, id;
  77.     PointI(int x_ = 0, int y_ = 0, int i = -1) : x(x_), y(y_), id(i) {}
  78.     friend ostream& operator<<(ostream& out, const PointI& u) {
  79.         return out << "(" << u.x << ", " << u.y << ", " << u.id << ")";
  80.     }
  81. };
  82. int n, m;
  83. vector<Point> poly; 
  84. vector<PointI> queries;
  85. bool read() {
  86.     n = getnum();
  87.     if (feof(stdin)) return false;
  88.     m = getnum();
  89.     poly.resize(n);
  90.     queries.resize(m);
  91.     for (auto& [x, y]: poly) {
  92.         x = getnum();
  93.         y = getnum();
  94.     }
  95.     int id = 0;
  96.     for (auto& [x, y, i]: queries) {
  97.         x = getnum();
  98.         y = getnum();
  99.         i = id++;
  100.     }
  101.     return true;
  102. }
  103.  
  104. int l2(int num) {
  105.     return 31 - __builtin_clz(num);
  106. }
  107.  
  108. void tle_assert(bool x) {
  109. #ifndef LOCAL
  110.     while (!x);
  111. #endif
  112. }
  113.  
  114. vector<llong> combine(vector<llong> u, const vector<llong>& v) {
  115.     rep(i, len(u)) u[i] = min(u[i], v[i]);
  116.     return u;
  117. }
  118.  
  119. vector<llong> min_hor() {
  120.     vector<pair<llong, llong>> upd;
  121.     vector<PointI> qr;
  122.     auto prev = poly.back();
  123.     for (auto cur: poly) {
  124.         if (cur.y == prev.y) {
  125.             upd.emplace_back(cur.y, cur.x);
  126.             upd.emplace_back(prev.y, prev.x);
  127.         }
  128.         prev = cur;
  129.     }
  130.  
  131.     for (auto [x, y, id]: queries) qr.emplace_back(y, x, id);
  132.     sort(upd.begin(), upd.end());
  133.     sort(qr.begin(), qr.end(), [&](const PointI& u, const PointI& v) { return u.x < v.x; });
  134.     vector<llong> ans(m);
  135.     set<llong> ranges;
  136.     int ptr = 0;
  137.     for (auto [qpos, qpoint, id]: qr) {
  138.         while (ptr < len(upd)) {
  139.             auto [upos, endpoint] = upd[ptr];
  140.             if (upos > qpos) break;
  141.             ++ptr;
  142.             if (ranges.count(endpoint)) ranges.erase(endpoint);
  143.             else ranges.insert(endpoint);
  144.         }
  145.         ans[id] = *ranges.upper_bound(qpoint) - qpoint;
  146.     }
  147.     return ans;
  148. }
  149.  
  150. vector<llong> min_hor_diag() {
  151.     vector<llong> y_vals;
  152.     for (auto& [x, y, id]: queries) y_vals.push_back(y);
  153.     sort(y_vals.begin(), y_vals.end());
  154.     y_vals.erase(unique(y_vals.begin(), y_vals.end()), y_vals.end());
  155.     auto index = [&](llong val) {
  156.         return (int)(lower_bound(y_vals.begin(), y_vals.end(), val) - y_vals.begin());
  157.     };
  158.     vector<vector<PointI>> qr(2 * m);
  159.     vector<vector<pair<llong, llong>>> upd(2 * m);
  160.  
  161.     sort(queries.rbegin(), queries.rend(), [](const PointI& u, const PointI& v) {
  162.             return u.x - u.y < v.x - v.y;
  163.             });
  164.     for (auto p: queries) {
  165.         int i = index(p.y);
  166.         for (i += m; i > 0; i >>= 1) 
  167.             qr[i].push_back(p);
  168.     }
  169.  
  170.     vector<Point> precal_upd;
  171.     auto prev = poly.back();
  172.     for (auto cur: poly) {
  173.         if (prev.y != cur.y) {
  174.             precal_upd.emplace_back(prev.x, prev.y);
  175.         }
  176.         prev = cur;
  177.     }
  178.     sort(precal_upd.rbegin(), precal_upd.rend(), [&](const auto& u, const auto& v) {
  179.             return u.x - u.y < v.x - v.y;
  180.             });
  181.  
  182.     for (auto [x, y]: precal_upd) {
  183.         llong diff = x - y;
  184.         int l = m, r = index(y + 1) + m;
  185.         for (; l < r; l >>= 1, r >>= 1) {
  186.             if (l & 1) upd[l++].emplace_back(diff, x);
  187.             if (r & 1) upd[--r].emplace_back(diff, x);
  188.         }
  189.     }
  190.  
  191.     vector<llong> ans(m, INT_MAX);
  192.     for (int root = 1; root < 2 * m; ++root) {
  193.         if (!len(qr[root]) or !len(upd[root])) continue;
  194.         llong cur_min_x = INT_MAX;
  195.         int ptr = 0;
  196.         for (auto [x, y, id]: qr[root]) {
  197.             llong cur_diff = x - y;
  198.             while (ptr < len(upd[root])) {
  199.                 auto [diff, px] = upd[root][ptr];
  200.                 if (diff < cur_diff) break;
  201.                 ++ptr;
  202.                 cur_min_x = min(cur_min_x, px);
  203.             }
  204.             ans[id] = min(ans[id], cur_min_x - x);
  205.         }
  206.     }
  207.     return ans;
  208. }
  209.  
  210. vector<llong> solve_single_axis() {
  211.     return combine(min_hor(), min_hor_diag());
  212. }
  213.  
  214. vector<llong> solve() {
  215.     auto ans = solve_single_axis();
  216.     for (auto& [x, y]: poly) swap(x, y);
  217.     for (auto& [x, y, id]: queries) swap(x, y);
  218.     reverse(poly.begin(), poly.end());
  219.     // cout << "Polygon" << endl; 
  220.     // for (auto [x, y]: poly) { 
  221.         // cout << x << ' ' << y << endl; 
  222.     // } 
  223.     // cout << endl; 
  224.  
  225.     return combine(ans, solve_single_axis());
  226. }
  227.  
  228. int main(void) {
  229. #ifdef LOCAL
  230.     freopen("main.inp", "r", stdin);
  231.     freopen("main.out", "w", stdout);
  232.     freopen(".log", "w", stderr);
  233. #endif
  234.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  235.     while (read()) {
  236.         auto ans = solve();
  237.         for (auto i: ans) cout << i << '\n';
  238.     }
  239.  
  240.     return 0;
  241. }
  242.  
  243. // vim: foldmethod=marker
  244.  
Success #stdin #stdout 0s 4752KB
comments (?)
stdin
copy 
4 3
0 0
4 0
4 4
0 4
1 1
2 2
3 3
12 12
3050 2000
2000 2000
2000 3635
-2000 3635
-2000 2000
-2590 2000
-2590 -2000
-2000 -2000
-2000 -3481
2000 -3481
2000 -2000
3050 -2000
1415 -2882
-1100 498
-827 -3331
-114 -542
-1887 3485
-1606 -1463
-768 880
-1261 1180
330 2648
-1017 -2886
-1213 -585
-2025 -1966
stdout
copy 
3
2
1
585
3100
2827
2542
150
3606
2755
2455
987
3017
3213
3966
https://ideone.com/80D2L5
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

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!