<ulclass="metadata page-metadata"data-bi-name="page info"lang="en-us"dir="ltr">

Last update:

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="September 21, 202500:15:21 UTC">September 21, 2025</span>&emsp;

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="September 21, 202522:22:46 UTC">September 21, 2025</span>&emsp;

<h2id="solution-in-on-log-n-with-dynamic-programming-and-binary-search">Solution in<spanclass="arithmatex">$O(n \log n)$</span> with dynamic programming and binary search<aclass="headerlink"href="#solution-in-on-log-n-with-dynamic-programming-and-binary-search"title="Permanent link">&para;</a></h2>

<p>In order to obtain a faster solution for the problem, we construct a different dynamic programming solution that runs in<spanclass="arithmatex">$O(n^2)$</span>, and then later improve it to<spanclass="arithmatex">$O(n \log n)$</span>.</p>

<p>We will use the dynamic programming array<spanclass="arithmatex">$d[0 \dots n]$</span>.

This time<spanclass="arithmatex">$d[l]$</span> doesn'tcorresponds to the element<spanclass="arithmatex">$a[i]$</span> or to a prefix of the array.

This time<spanclass="arithmatex">$d[l]$</span> doesn'tcorrespond to the element<spanclass="arithmatex">$a[i]$</span> or to a prefix of the array.

<spanclass="arithmatex">$d[l]$</span> will be the smallest element at which an increasing subsequence of length<spanclass="arithmatex">$l$</span> ends.</p>

<p>Initially we assume<spanclass="arithmatex">$d[0] = -\infty$</span> and for all other lengths<spanclass="arithmatex">$d[l] = \infty$</span>.</p>

<p>We will again gradually process the numbers, first<spanclass="arithmatex">$a[0]$</span>, then<spanclass="arithmatex">$a[1]$</span>, etc, and in each step maintain the array<spanclass="arithmatex">$d[]$</span> so that it is up to date.</p>

<ulclass="metadata page-metadata"data-bi-name="page info"lang="en-us"dir="ltr">

<spanclass="contributors-text">Contributors:</span>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (99.72%)</li><li><ahref="https://github.com/arjunUpatel"title="arjunUpatel"data-bi-name="contributorprofile"target="_blank">arjunUpatel</a> (0.28%)</li></ul>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (100.0%)</li></ul>

<ulclass="metadata page-metadata"data-bi-name="page info"lang="en-us"dir="ltr">

Last update:

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="August 23, 202522:03:07 UTC">August 23, 2025</span>&emsp;

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="September 21, 202509:00:38 UTC">September 21, 2025</span>&emsp;

<spanclass="c1">// Choose some good generator of randomness for the shuffle</span>

<spanclass="n">mt19937_64</span><spanclass="w"></span><spanclass="nf">gen</span><spanclass="p">(...);</span>

<spanclass="n">mec</span><spanclass="w"></span><spanclass="nf">enclosing_circle</span><spanclass="p">(</span><spanclass="n">vector</span><spanclass="o">&lt;</span><spanclass="n">point</span><spanclass="o">&gt;</span><spanclass="w"></span><spanclass="o">&amp;</span><spanclass="n">p</span><spanclass="p">)</span><spanclass="w"></span><spanclass="p">{</span>

<spanclass="w"></span><spanclass="kt">int</span><spanclass="w"></span><spanclass="n">n</span><spanclass="w"></span><spanclass="o">=</span><spanclass="w"></span><spanclass="n">p</span><spanclass="p">.</span><spanclass="n">size</span><spanclass="p">();</span>

<spanclass="w"></span><spanclass="n">ranges</span><spanclass="o">::</span><spanclass="n">shuffle</span><spanclass="p">(</span><spanclass="n">p</span><spanclass="p">,</span><spanclass="w"></span><spanclass="n">gen</span><spanclass="p">);</span>

<spanclass="w"></span><spanclass="k">auto</span><spanclass="w"></span><spanclass="n">C</span><spanclass="w"></span><spanclass="o">=</span><spanclass="w"></span><spanclass="n">mec</span><spanclass="p">{</span><spanclass="n">p</span><spanclass="p">[</span><spanclass="mi">0</span><spanclass="p">],</span><spanclass="w"></span><spanclass="n">p</span><spanclass="p">[</span><spanclass="mi">1</span><spanclass="p">]};</span>

<spanclass="w"></span><spanclass="k">for</span><spanclass="p">(</span><spanclass="kt">int</span><spanclass="w"></span><spanclass="n">i</span><spanclass="w"></span><spanclass="o">=</span><spanclass="w"></span><spanclass="mi">0</span><spanclass="p">;</span><spanclass="w"></span><spanclass="n">i</span><spanclass="w"></span><spanclass="o">&lt;</span><spanclass="w"></span><spanclass="n">n</span><spanclass="p">;</span><spanclass="w"></span><spanclass="n">i</span><spanclass="o">++</span><spanclass="p">)</span><spanclass="w"></span><spanclass="p">{</span>

<divclass="arithmatex">$$

\angle azb + \angle bca

$$</div>

<p>In a<ahref="https://en.wikipedia.org/wiki/Cyclic_quadrilateral">cyclic quadrilateral</a>, if<spanclass="arithmatex">$c$</span> and<spanclass="arithmatex">$z$</span> are from the same side of<spanclass="arithmatex">$ab$</span>, then the angles are equal, and willad up to<spanclass="arithmatex">$0^\circ$</span> when summed up signed (i.e. positive if counter-clockwise and negative if clockwise). Correspondingly, if<spanclass="arithmatex">$c$</span> and<spanclass="arithmatex">$z$</span> are on the opposite sides, the angles will add up to<spanclass="arithmatex">$180^\circ$</span>.</p>

<p>In a<ahref="https://en.wikipedia.org/wiki/Cyclic_quadrilateral">cyclic quadrilateral</a>, if<spanclass="arithmatex">$c$</span> and<spanclass="arithmatex">$z$</span> are from the same side of<spanclass="arithmatex">$ab$</span>, then the angles are equal, and willadd up to<spanclass="arithmatex">$0^\circ$</span> when summed up signed (i.e. positive if counter-clockwise and negative if clockwise). Correspondingly, if<spanclass="arithmatex">$c$</span> and<spanclass="arithmatex">$z$</span> are on the opposite sides, the angles will add up to<spanclass="arithmatex">$180^\circ$</span>.</p>

<imgsrc="https://upload.wikimedia.org/wikipedia/commons/3/30/Opposing_inscribed_angles.svg">

<ulclass="metadata page-metadata"data-bi-name="page info"lang="en-us"dir="ltr">

<spanclass="contributors-text">Contributors:</span>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (98.09%)</li><li><ahref="https://github.com/MKLOL"title="MKLOL"data-bi-name="contributorprofile"target="_blank">MKLOL</a> (1.91%)</li></ul>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (97.14%)</li><li><ahref="https://github.com/MKLOL"title="MKLOL"data-bi-name="contributorprofile"target="_blank">MKLOL</a> (1.9%)</li><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (0.95%)</li></ul>

<ulclass="md-nav__list"data-md-component="toc"data-md-scrollfix>

<liclass="md-nav__item">

<ahref="#become-a-contributor"class="md-nav__link">

<spanclass="md-ellipsis">

Become a Contributor

<liclass="md-nav__item">

<ahref="#sponsor-us"class="md-nav__link">

<spanclass="md-ellipsis">

Sponsor Us

<liclass="md-nav__item">

<ahref="#changelog"class="md-nav__link">

<spanclass="md-ellipsis">

<liclass="md-nav__item">

<ahref="#contributing"class="md-nav__link">

<spanclass="md-ellipsis">

Contributing

and data structures especially popular in field of competitive programming.

Moreover we want to improve the collected knowledge by extending the articles

and adding new articles to the collection.</p>

<p>We're an ad-free, volunteer-run website that's free for everyone. Users can contribute articles or help sponsor bounties on articles for greater algorithmic coverage. Your help is greatly appreciated.</p>

<p>Compiled pages are published at<ahref="https://cp-algorithms.com/">https://cp-algorithms.com/</a>.</p>

<h2id="become-a-contributor">Become a Contributor<aclass="headerlink"href="#become-a-contributor"title="Permanent link">&para;</a></h2>

<li><ahref="https://cp-algorithms.com/contrib.html">How to Contribute</a></li>

<li><ahref="https://cp-algorithms.com/code_of_conduct.html">Code of Conduct</a></li>

<li><ahref="https://cp-algorithms.com/preview.html">Test-Your-Page Form</a></li>

<h2id="sponsor-us">Sponsor Us<aclass="headerlink"href="#sponsor-us"title="Permanent link">&para;</a></h2>

<li><ahref="https://github.com/sponsors/cp-algorithms">Become a Financial Supporter</a></li>

<h2id="changelog">Changelog<aclass="headerlink"href="#changelog"title="Permanent link">&para;</a></h2>

<li>August, 2025: Overhaul of CP-Algorithms<ahref="https://github.com/sponsors/cp-algorithms">donation system</a>. Please consider supporting us, so that we can grow!</li>

<p>Full list of updates:<ahref="https://github.com/cp-algorithms/cp-algorithms/commits/main">Commit History</a></p>

<p>Full list of articles:<ahref="https://cp-algorithms.com/navigation.html">Navigation</a></p>

<h2id="contributing">Contributing<aclass="headerlink"href="#contributing"title="Permanent link">&para;</a></h2>

<li><ahref="https://cp-algorithms.com/contrib.html">Information for contributors</a></li>

<li><ahref="https://cp-algorithms.com/code_of_conduct.html">Code of conduct</a></li>

<li><ahref="https://cp-algorithms.com/preview.html">Test-Your-Page form</a></li>

<ulclass="metadata page-metadata"data-bi-name="page info"lang="en-us"dir="ltr">

<spanclass="contributors-text">Contributors:</span>

Moreover we want to improve the collected knowledge by extending the articles

and adding new articles to the collection.

We're an ad-free, volunteer-run website that's free for everyone. Users can contribute articles or help sponsor bounties on articles for greater algorithmic coverage. Your help is greatly appreciated.

Compiled pages are published at [https://cp-algorithms.com/](https://cp-algorithms.com/).

## Become a Contributor

- [How to Contribute](https://cp-algorithms.com/contrib.html)

- [Code of Conduct](https://cp-algorithms.com/code_of_conduct.html)

- [Test-Your-Page Form](https://cp-algorithms.com/preview.html)

## Sponsor Us

- [Become a Financial Supporter](https://github.com/sponsors/cp-algorithms)

## Changelog

- August, 2025: Overhaul of CP-Algorithms [donation system](https://github.com/sponsors/cp-algorithms). Please consider supporting us, so that we can grow!

Full list of articles: [Navigation](https://cp-algorithms.com/navigation.html)

## Contributing

- [Information for contributors](https://cp-algorithms.com/contrib.html)

- [Code of conduct](https://cp-algorithms.com/code_of_conduct.html)

- [Test-Your-Page form](https://cp-algorithms.com/preview.html)