G - Division Point Hull Editorial by en_translator
We employ 0-based indexing; i.e. let \(P_0,P_1,\dots,P_{N-1}\) denote the given points.
We use the following notations in this editorial. Here, \(A\) and \(B\) are sets of points, and \(r\) is a real number.
- \(\operatorname{conv}(A)\): the convex hull of \(A\). Let \(\operatorname{conv}(\emptyset)=\emptyset\).
- \(r\cdot A=\{r\cdot a\mid a\in A\}\) (where \(r\cdot a\) is obtained by multiplying each component of \(a\) by \(r\)).
- \(A+B=\{a+b\mid a\in A,b\in B\}\): Minkowski sum (where \(a+b\) is the component-wise sum of \(a\) and \(b\)).
Apply the divide-and-conquer algorithm.
Put \(P[l,r)\coloneqq\{P_i\mid l\leq i< r\}\) and \(Q[l,r)\coloneqq\{Q_{i,j}\mid l \leq i\lt j\lt r\}\). Then \(Q[l,l+1)=\emptyset\). For \(r-l\geq 2\), let \(m=\left\lfloor\frac{l+r}{2}\right\rfloor\); then
\[\begin{aligned} Q[l,r) &=Q[l,m)\cup Q[m,r)\cup\left\{\frac{q\cdot u+p\cdot v}{p+q} \mid u\in P[l,m),v\in P[m,r)\right\}\\ &=Q[l,m)\cup Q[m,r)\cup\left(\frac{q}{p+q}\cdot P[l,m)+\frac{p}{p+q}\cdot P[m,r)\right) \end{aligned}\]
Defining \(q'=\frac{q}{p+q}\) and \(p'=\frac{p}{p+q}\), taking the convex hull of the both hand sides yields (note that \(\operatorname{conv}(A+B)=\operatorname{conv}(A)+\operatorname{conv}(B)\)):
\[\begin{aligned} \operatorname{conv}(Q[l,r)) &=\operatorname{conv}\bigl(Q[l,m)\cup Q[m,r)\cup\left(q'\cdot P[l,m)+p'\cdot P[m,r)\right)\bigr)\\ &=\operatorname{conv}\bigl(\operatorname{conv}(Q[l,m))\cup \operatorname{conv}(Q[m,r))\cup\operatorname{conv}\left(q'\cdot P[l,m)+p'\cdot P[m,r)\right)\bigr)\\ &=\operatorname{conv}\bigl(\operatorname{conv}(Q[l,m))\cup \operatorname{conv}(Q[m,r))\cup\left(q'\cdot \operatorname{conv}(P[l,m))+p'\cdot \operatorname{conv}(P[m,r))\right)\bigr). \end{aligned}\]
Consider the complexity.
The convex hull of \(n\) points ca be obtained in \(O(n\log n)\) time. Also, the Minkowski sum of convex polygons can be obtained in linear time of the sum of the numbers of vertices, by merging the edge vectors by their azimuth. Since we can prove that \(\operatorname{conv}(Q[l,r))\) has \(O(r-l)\) vertices (see Appendix), the time complexity \(T(n)\) required to compute \(\operatorname{conv}(Q[l,r))\) satisfies \(T(n)=2T(n/2)+O(n\log n)\); hence \(T(n)=O(n(\log n)^2)\).
Thus, the sought convex hull \(\operatorname{conv}(Q[0,N))\) can be obtained in a total of \(O(N(\log N)^2)\) time.
The area can be computed in linear tie of the number of vertices of the convex hull. In implementation, all arithmetic operations can be done on integers by multiplying all coordinates by \((p+q)\). 実装例(C++)
Instead of directly computing \(\operatorname{conv}(Q[l,r))\), one can incrementally obtain \(q'\cdot \operatorname{conv}(P[l,m))+p'\cdot \operatorname{conv}(P[m,r))\) during the divide-and-conquer, and finally find their convex hull. This also yields an \(O(N(\log N)^2)\) solution.
The problem can even be solved in a total of \(O(N\log N)\) time, by performing the sort required for finding the convex hull in the manner of merge sort, during the divide-and-conquer. Sample code (C++)
Appendix: evaluation of the number of vertices of \(\operatorname{conv}(Q[l,r))\)
We will show that \(\operatorname{conv}(Q[0,N))\) has \(O(N)\) vertices; in particular, at most \(3N\) vertices.
Let \(M\) be the number of distinct points in \(P_0,\dots,P_{N-1}\), and \(C\) be their convex hull. Let \(h_1\) be the number of points that occur exactly once in \(P_0,P_1,\dots,P_{N-1}\), \(h_2\) be those occurring twice or more, and \(h=h_1+h_2\).
For any vertex \(x\) of \(\operatorname{conv}(Q[0,N))\), the property of a convex hull guarantees the existence of a unit vector \(v\) such that:
- \(\{Q_{i,j} \mid (i,j) \in \argmax_{(i,j)}(v\cdot Q_{i,j})\}=\{x\}\),
- \(\#\{P_i \mid i\in\argmax_i(v\cdot P_i)\}=1\).
Let \(R\) be the only point contained in \(\{P_i \mid i\in\argmax_i(v\cdot P_i)\}\).
First, if \(\#\argmax_i (v\cdot P_i) \geq 2\), taking \(i,j\in\argmax_i (v\cdot P_i)\) with \(i<j\) satisfies \(P_i=P_j=Q_{i,j}=R\). Since \(v\cdot Q_{i',j'}<v\cdot R\) for any \(Q_{i',j'}\) whose at least one of the endpoint is not \(R\), it follows that \(x=R\). There are at most \(h_2\) such points \(x\).
Next, if \(\#\argmax_i (v\cdot P_i)=1\), for \(k\in \argmax_i (v\cdot P_i)\) and for the \((i,j)\) that maximizes \(v\cdot Q_{i,j}\), at least one of \(i\) and \(j\) equals \(k\). (If it were not, replacing one with \(k\) makes \(v\cdot Q_{i,j}\) larger.)
Hence, the following two types must be considered:
- (A) \(i<k=j\) and \(v\cdot P_i=\max_{i'<k}(v\cdot P_{i'})\).
- (B) \(i=k<j\) and \(v\cdot P_j=\max_{k<j'}(v\cdot P_{j'})\).
Let \(A\) and \(B\) be the set of points that are \(\operatorname{conv}(Q[0,N))\) and satisfies (A) and (B) for some \(v\), respectively.
We will evaluate \(\#A\). Let \(C_k=\operatorname{conv}(P[0,k))\). For an index to be applicable for \(k\) in (A), it is necessary that \(P_k\) is a vertex of \(C\), and that point occurs exactly once in \(P_0,\dots,P_{N-1}\); there are exactly \(h_1\) such indices. For such a \(k\), consider \(P_k\) joining \(C_k\) to form \(C_{k+1}\). Since \(P_k\) is a vertex of the final convex hull \(C\), it is outside \(C_k\), so the boundary of \(C_k\) visible from \(C_k\) forms a contiguous vertex sequence. Also, since it is necessary that \(\argmax_i (v\cdot P_i)=\{k\}\), the points applicable for \(P_i\) in (A) is limited to the vertices in this sequence.

All vertices in this sequence except for the endpoints, marked with circles in the figure, become no longer a vertex of the convex hull once \(P_k\) joins, and never becomes a vertex again. Conversely, a vertex of \(C\) is always present in the resulting convex hull. Hence, throughout all \(k\), there are at most \((M-h)\) vertices that can occur in the interior of such a vertex sequence. On the other hand, the number of the points on the endpoints of the sequence (marked by squares) is at most \(2\), and the indices \(k\) that needs to be considered is \(h_1\), so the number of points that can appear as an endpoint is at most \(2h_1\), including duplicates. Hence, we obtain \(\#A\leq (M-h)+2h_1\). Likewise, \(\#B\leq (M-h)+2h_1\).
Next, we will evaluate \(\#(A\cap B)\). Consider an edge of \(C\) such that:
- both endpoints occur exactly once in \(P\), and
- the interior (where the endpoints are excluded), does not contain another point in \(P\).
Let \(P_a\) and \(P_b\) be the endpoints of such an edge \((a<b)\). Consider a vector \(v\) obtained by as the normal vector of the edge pointing toward the exterior, rotated slightly toward \(P_b\). Then \(v\cdot P_b>v\cdot P_a>v\cdot P_i\ (i\neq a,b)\), so \(Q_{a,b}\in A\). Meanwhile, rotating the normal vector slightly toward \(P_a\) swaps \(a\) and \(b\), so we obtain \(Q_{a,b}\in B\). Hence, for each such edge of \(C\), we obtain one element of \(A\cap B\).
\(C\) has \(h\) edges, of which at most \(2h_2\) edges have an endpoint that occurs twice or more in \(P\), and at most \((M-h)\) edges have another point in \(P\) in the interior (where the endpoints are excluded). Therefore, there are at least \(\max(0,h-2h_2-(M-h))=\max(0,2h_1-M)\) edges satisfying the two conditions above, yielding
\[ \#(A\cap B)\geq \max(0,2h_1-M). \]
To wrap up, the number of vertices \(K\) of \(\operatorname{conv}(Q[0,N))\) satisfies
\[ \begin{aligned} K &\leq h_2+\#(A\cup B)\\ &= h_2+\#A+\#B-\#(A\cap B)\\ &\leq 2M+2h_1-h_2-\max(0,2h_1-M) \end{aligned} \]
Separate discussions depending on \(2h_1\leq M\) both lead to \(K\leq 3M\leq 3N\), in particular implying \(\operatorname{conv}(Q[0,N))\) has \(O(N)\) vertices.
The same discussion can be applied to any interval \([l,r)\), so \(\operatorname{conv}(Q[l,r))\) has \(O(r-l)\) vertices.
It is unknown whether there is a generic bound below \(3N\), and whether a case close to this upper bound can be actually constructed……