fork(3) download 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <numeric>
  4. #include <cstdint>
  5. #include <cstring>
  6. using namespace std;
  7.  
  8. using ind_t = uint_least8_t;
  9. using pos_t = int32_t;
  10. using tangent_t = float;
  11.  
  12. constexpr size_t kSizeArr = 256;
  13. constexpr size_t kShift = 16;
  14. constexpr pos_t kMask = (1 << kShift) - 1;
  15. constexpr ind_t kPruneStep = 8;
  16.  
  17. pos_t points[kSizeArr];
  18. tangent_t tangents[kSizeArr];
  19. ind_t tmp[kSizeArr];
  20. ind_t sorted[kSizeArr][kSizeArr];
  21. ind_t lefts[kSizeArr][kSizeArr];
  22. ind_t memorize[kSizeArr][kSizeArr];
  23. size_t n;
  24.  
  25. void readInput()
  26. {
  27.     cin >> n;
  28.  
  29.     for (size_t i = 0; i < n; ++i)
  30.     {
  31.         pos_t x, y;
  32.         cin >> x >> y;
  33.         points[i] = (x << kShift) + kMask - y;
  34.     }
  35. }
  36.  
  37. void order()
  38. {
  39.     sort(points, points + n);
  40.  
  41.     for (size_t i = 0; i < n; ++i)
  42.         points[i] = (points[i] & ~kMask) + kMask - (points[i] & kMask);
  43. }
  44.  
  45. void preprocess()
  46. {
  47.     for (size_t i_center = 0; i_center < n; ++i_center)
  48.     {
  49.         ind_t ind = 0;
  50.         const pos_t x_center = points[i_center] >> kShift;
  51.         const pos_t y_center = points[i_center] & kMask;
  52.         const auto nm1 = n - 1;
  53.         iota(tmp, tmp + n, 0);
  54.  
  55.         for (size_t i_pt = 0; i_pt < n; ++i_pt)
  56.         {
  57.             const pos_t x = points[i_pt] >> kShift;
  58.             const pos_t y = points[i_pt] & kMask;
  59.  
  60.             tangents[i_pt] =
  61.                 static_cast<tangent_t>(y - y_center) /
  62.                 static_cast<tangent_t>(x - x_center);
  63.         }
  64.  
  65.         tmp[i_center] = tmp[nm1];
  66.         tangents[i_center] = tangents[nm1];
  67.  
  68.         sort(tmp, tmp + nm1, [&](ind_t l, ind_t r)
  69.         {
  70.             return tangents[l] < tangents[r];
  71.         });
  72.  
  73.         const auto mkLeft = [&](size_t ii)
  74.         {
  75.             lefts[tmp[ii]][i_center] = ind;
  76.         };
  77.  
  78.         const auto mkSorted = [&](size_t ii)
  79.         {
  80.             sorted[i_center][ind++] = tmp[ii];
  81.         };
  82.  
  83.         for (size_t i = 0; i < nm1; ++i)
  84.         {
  85.             if ((points[tmp[i]] >> kShift) < x_center)
  86.                 mkLeft(i);
  87.             else
  88.                 mkSorted(i);
  89.         }
  90.  
  91.         for (size_t i = 0; i < nm1; ++i)
  92.         {
  93.             if ((points[tmp[i]] >> kShift) >= x_center)
  94.                 mkLeft(i);
  95.             else
  96.                 mkSorted(i);
  97.         }
  98.  
  99.         if ((points[tmp[nm1 - 1]] >> kShift) == x_center &&
  100.             (points[tmp[nm1 - 1]] & kMask) > y_center
  101.         )
  102.             lefts[tmp[nm1 - 1]][i_center] = 0;
  103.  
  104.         sorted[i_center][ind] = static_cast<ind_t>(i_center);
  105.     }
  106. }
  107.  
  108. void prune(size_t from, size_t to)
  109. {
  110.     for (size_t i = to; i < n; ++i)
  111.     {
  112.         size_t new_j = 0;
  113.         ind_t delta = 0;
  114.         for (size_t j = 0; j < n - from; ++j)
  115.         {
  116.             tmp[j] = delta;
  117.  
  118.             if (sorted[i][j] < to)
  119.                 ++delta;
  120.             else
  121.                 sorted[i][new_j++] = sorted[i][j];
  122.         }
  123.  
  124.         for (size_t j = to; j < n; ++j)
  125.             lefts[j][i] = static_cast<ind_t>(lefts[j][i] - tmp[lefts[j][i]]);
  126.     }
  127. }
  128.  
  129. unsigned dpStep(ind_t i_left, ind_t from, ind_t to_ind)
  130. {
  131.     ind_t child = sorted[from][to_ind];
  132.  
  133.     while (child < i_left)
  134.         child = sorted[from][++to_ind];
  135.  
  136.     if (child == i_left)
  137.         return 1;
  138.  
  139.     if (auto v = memorize[from][child])
  140.         return v;
  141.  
  142.     const auto x = max(dpStep(i_left, child, lefts[from][child]) + 1,
  143.                        dpStep(i_left, from, static_cast<ind_t>(to_ind + 1)));
  144.  
  145.     memorize[from][child] = static_cast<ind_t>(x);
  146.     return x;
  147. }
  148.  
  149. unsigned dp(ind_t i_left)
  150. {
  151.     return dpStep(i_left, i_left, 0);
  152. }
  153.  
  154. unsigned solve()
  155. {
  156.     unsigned best = 0;
  157.  
  158.     ind_t i_prune = kPruneStep;
  159.     for (ind_t i_left = 0; i_left < n - best; ++i_left)
  160.     {
  161.         memset((void*)memorize, 0, sizeof(memorize));
  162.         best = max(best, dp(i_left));
  163.  
  164.         if (--i_prune == 0)
  165.         {
  166.             i_prune = kPruneStep;
  167.             prune(i_left + 1 - kPruneStep, i_left + 1);
  168.         }
  169.     }
  170.  
  171.     return best;
  172. }
  173.  
  174. int main()
  175. {
  176.     readInput();
  177.     order();
  178.     preprocess();
  179.     cout << solve() << '\n';
  180. }
  181.  
Success #stdin #stdout 0s 3496KB
comments (?)
stdin 
4
0 0
9 0
3 9
2 1
stdout 
3
https://ideone.com/08fpMn
language:
C++14 (gcc 8.3)
created:
11 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!