src/geo2d/maxv_cvh_cnt/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../ds/l/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | // max number of vertices in vp which forms a convex hull | ||
| 8 | template <class FP> | ||
| 9 | 20 | CEXP u32 maxv_cvh_cnt(vec<point<FP>> CR vp) NE { | |
| 10 | 20 | cu32 n = (u32)vp.size(); | |
| 11 | |||
| 12 | struct TIFA { | ||
| 13 | line<FP> ln; | ||
| 14 | u32 l, r; | ||
| 15 | 448558 | CEXP TIFA(u32 l, u32 r, point<FP> CR pl, point<FP> CR pr) NE : ln(pl, pr), l(l), r(r) {} | |
| 16 | 8379927 | CEXP auto operator<=>(TIFA CR r) CNE { return ln <=> r.ln; } | |
| 17 | CEXP bool operator==(TIFA CR r) CNE = default; | ||
| 18 | }; | ||
| 19 | 20 | vec<TIFA> vl; | |
| 20 |
2/2✓ Branch 0 taken 2336 times.
✓ Branch 1 taken 20 times.
|
2356 | flt_ (u32, i, 0, n) |
| 21 |
2/2✓ Branch 0 taken 450894 times.
✓ Branch 1 taken 2336 times.
|
453230 | flt_ (u32, j, 0, n) |
| 22 |
2/2✓ Branch 0 taken 448558 times.
✓ Branch 1 taken 2336 times.
|
450894 | if (i != j) vl.emplace_back(i, j, vp[i], vp[j]); |
| 23 | 20 | sort(vl); | |
| 24 | 20 | veci f(n + 1); | |
| 25 | 20 | u32 ans = 0; | |
| 26 |
2/2✓ Branch 0 taken 2336 times.
✓ Branch 1 taken 20 times.
|
2356 | flt_ (u32, i, 0, n) { |
| 27 | 2336 | fill(f, INT32_MIN), f[i] = 0; | |
| 28 |
2/2✓ Branch 8 taken 97381562 times.
✓ Branch 9 taken 2336 times.
|
97383898 | flt_ (u32, j, 0, (u32)vl.size()) f[vl[j].r] = max(f[vl[j].r], f[vl[j].l] + 1); |
| 29 | 2336 | ans = (u32)max((i32)ans, f[i]); | |
| 30 | } | ||
| 31 | 40 | return ans; | |
| 32 | 20 | } | |
| 33 | |||
| 34 | } // namespace tifa_libs | ||
| 35 |