StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The question is quite unclear but it appears from comment "I mean find that a in f(x)=ax to have maximum points which are valid and their amount doesn't exceed some value X" that you want to find <code>a</code> such that <code>N(a)=X</code>, where by <code>N(a)</code> I mean number of points right of the y axis and above line <code>y=ax</code>; or if no such <code>a</code> exists, find <code>a</code> such that <code>m = N(a)<X</code> and <code>N(b)<m</code> implies <code>N(b)<X</code>.</p> <p>Here's an O(n*ln(n)) algorithm: For each point <code>p</code>, excluding any <code>p</code> below <code>y=0</code>, compute slope M_p as ratio of <code>p</code>'s y and x coordinates, or DBL_MAX if x=0. Sort the M's into ascending order (this is the O(n*ln(n)) step), and call the sorted array <code>S</code>. </p> <p>Now we will set up an array <code>T</code> such that when any <code>X</code> is given, <code>S[T[X-1]]</code> is a slope that will place X points on or above that slope:</p> <pre><code> S[n] = DBL_MAX; for (k=0, j=n-1; k<=n; --j) { T[j] = k; do ++k; while (S[k]==S[k-1] && k<=n); } </code></pre> <p>Thereafter, let any X be given. Let <code>h = T[X-1]</code>. If <code>h<n</code> then <code>N(S[h]) <= X</code>; if <code>h==n</code>, there are multiple points on the Y axis and no finite slope will work.</p> <p>This algorithm uses time O(n*ln(n)) and space O(n) to preprocess a set of n first-quadrant points, and thereafter uses time O(1) to find an <code>a</code> for any given <code>X, 0 < X <= n,</code> such that <code>N(a) = X</code>, if such <code>a</code> exists, else returns <code>a</code> such that <code>N(a) < X < N(b)</code> if <code>b>a</code>, else returns DBL_MAX.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload