fork download
copy 
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <list>
  9. #include <time.h>
  10. #include <math.h>
  11. #include <random>
  12. #include <deque>
  13. #include <queue>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include <iomanip>
  18. #include <bitset>
  19. #include <sstream>
  20.  
  21. using namespace std;
  22.  
  23. typedef long long ll;
  24.  
  25. mt19937 rnd(228);
  26.  
  27. struct pt
  28. {
  29.     int x, y;
  30. };
  31.  
  32. pt operator - (const pt &a, const pt &b)
  33. {
  34.     return {a.x - b.x, a.y - b.y};
  35. }
  36.  
  37. ll abs(const pt &p)
  38. {
  39.     return p.x * (ll) p.x + p.y * (ll) p.y;
  40. }
  41.  
  42. ll operator * (const pt &a, const pt &b)
  43. {
  44.     return a.x * (ll) b.y - a.y * (ll) b.x;
  45. }
  46.  
  47. bool cmp(const pt &a, const pt &b)
  48. {
  49.     if (a.x != b.x)
  50.     {
  51.         return a.x < b.x;
  52.     }
  53.     else
  54.     {
  55.         return a.y < b.y;
  56.     }
  57. }
  58.  
  59. bool cw(pt a, pt b, pt c)
  60. {
  61. 	return a.x * (ll) (b.y - c.y) + b.x * (ll) (c.y - a.y) + c.x * (ll) (a.y - b.y) < 0;
  62. }
  63.  
  64. bool ccw(pt a, pt b, pt c)
  65. {
  66. 	return a.x * (ll) (b.y - c.y) + b.x * (ll) (c.y - a.y) + c.x * (ll) (a.y - b.y) > 0;
  67. }
  68.  
  69. vector <pt> p, up, down;
  70.  
  71. vector <pt> mrg(const vector <pt> &a, const vector <pt> &b)
  72. {
  73.     p.resize(a.size() + b.size());
  74.     merge(a.begin(), a.end(), b.begin(), b.end(), p.begin(), cmp);
  75.     return p;
  76. }
  77.  
  78. vector <pt> hull(const vector <pt> &e)
  79. {
  80.     if ((int) e.size() <= 3) return e;
  81.     up.clear();
  82.     down.clear();
  83.     p.clear();
  84.     pt p1 = e[0], p2 = e.back();
  85.     up.push_back(p1);
  86.     down.push_back(p1);
  87.     for (int i = 1; i < (int) e.size(); i++)
  88.     {
  89.         if (i == (int) e.size() - 1 || cw(p1, e[i], p2))
  90.         {
  91.             while ((int) up.size() >= 2 && !cw(up[(int) up.size() - 2], up[(int) up.size() - 1], e[i]))
  92.             {
  93.                 up.pop_back();
  94.             }
  95.             up.push_back(e[i]);
  96.         }
  97.         if (i == (int) e.size() - 1 || ccw(p1, e[i], p2))
  98.         {
  99.             while ((int) down.size() >= 2 && !ccw(down[(int) down.size() - 2], down[(int) down.size() - 1], e[i]))
  100.             {
  101.                 down.pop_back();
  102.             }
  103.             down.push_back(e[i]);
  104.         }
  105.     }
  106.     down.erase(down.begin());
  107.     down.pop_back();
  108.     return mrg(up, down);
  109. }
  110.  
  111. const int N = 1e5;
  112.  
  113. pt a[N];
  114. vector <pt> t[4 * N];
  115.  
  116.  
  117. void build(int v, int l, int r)
  118. {
  119.     if (r - l == 1)
  120.     {
  121.         t[v] = {a[l]};
  122.     }
  123.     else
  124.     {
  125.         int m = (l + r) / 2;
  126.         build(v * 2 + 1, l, m);
  127.         build(v * 2 + 2, m, r);
  128.         t[v] = mrg(t[v * 2 + 1], t[v * 2 + 2]);
  129.         t[v] = hull(t[v]);
  130.     }
  131. }
  132.  
  133. vector <pt> get(int v, int l, int r, int tl, int tr)
  134. {
  135.     if (tl >= r || tr <= l)
  136.     {
  137.         return {};
  138.     }
  139.     if (tl >= l && tr <= r)
  140.     {
  141.         return t[v];
  142.     }
  143.     else
  144.     {
  145.         int tm = (tl + tr) / 2;
  146.         return mrg(get(v * 2 + 1, l, r, tl, tm), get(v * 2 + 2, l, r, tm, tr));
  147.     }
  148. }
  149.  
  150. int n;
  151.  
  152. vector <pt> get(int l, int r)
  153. {
  154.     vector <pt> b = get(0, l, r + 1, 0, n);
  155.     b = hull(b);
  156.     return b;
  157. }
  158.  
  159. int main()
  160. {
  161. #ifdef ONPC
  162.     freopen("a.in", "r", stdin);
  163. #endif
  164.     ios::sync_with_stdio(0);
  165.     cin.tie(0);
  166.     cin >> n;
  167.     for (int i = 0; i < n; i++)
  168.     {
  169.         cin >> a[i].x >> a[i].y;
  170.     }
  171.     build(0, 0, n);
  172.     int q;
  173.     cin >> q;
  174.     while (q--)
  175.     {
  176.         int l, r;
  177.         cin >> l >> r;
  178.         l--, r--;
  179.         auto b = get(l, r);
  180.         ll ans = 0;
  181.         for (int i = 0; i < (int) b.size(); i++)
  182.         {
  183.             for (int j = i + 1; j < (int) b.size(); j++)
  184.             {
  185.                 ans = max(ans, abs(b[i] - b[j]));
  186.             }
  187.         }
  188.         cout << ans << '\n';
  189.     }
  190. }
  191.  
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fMGceG
language:
C++14 (gcc 8.3)
created:
6 years 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!