In one of the last stages of the 3rd Universal Cup, there was a not-so-nice problem (it required using fractions) that involved an algorithm for which I hadn't found a tutorial or much information on popular blogs. This approach was developed by me, and I appreciate any feedback on it or its implementation.

https://codeforces.me/gym/105657/problem/C

Parameters

• The polygon is convex
• The point is not strictly inside

What are the tangents to a polygon from a point?

The tangents of a polygon with respect to a point are the lines that pass through the point outside the polygon and touch the polygon at exactly one vertex or along one side, without crossing its interior.

Why are these useful?

• Solve difficult problems
• Solve problems related to visibility or trajectory where the polygon cannot be crossed.

Algorithm

To describe the algorithm, only the left tangent will be specified. At the end, it will be indicated what changes with respect to the right tangent.

The left tangent can be described using the cross product. For a point $$$P_i$$$ and the point $$$p$$$ (for which the tangents are computed), it can be considered the tangent if the cross product with respect to points $$$P_{i+1}$$$ and $$$P_{i-1}$$$ is less than or equal to zero:

Now, we will analyze the behavior of these signs in the following example.

Let us observe that the signs for point C are exactly as we require.
For points G, F, and E, the second condition is satisfied, and for points A, M, T, U, and V, the first condition is satisfied.
However, we can notice that it behaves like a unimodal function.

Thus, it is enough to find the first point for which the first condition is satisfied (in a counterclockwise direction).
To do this, we will do two things.

• Divide the convex hull into its lower and upper layers.
• Divide each layer into two parts to find the left and right tangents.

There will be cases where it would not be necessary to use a layer, as in the previous example. Determining when it would be necessary or not would only add more complexity and does not ultimately change the complexity.

The same example illustrated on the division.

When dividing the convex hull, we must take into account that if it is a single point that is farthest to the left (smallest x), it must be in both layers, and the same applies to the point farthest to the right (largest x).

To divide each layer into two parts, a binary search will be used.

Finally, the complexity analysis: a total of six binary searches will be performed, one for each layer and one for each of the four divisions of the polygon, resulting in $$$O(\log n)$$$.

int lk = m; if(Ps[0][m - 1] == Ps[1][0]) lk--; 

auto tang = [&](int l, int r, ld w, int kl) -> int {
    int res = min(l, r);
        while(l <= r){
       int m = (l + r) / 2;
       ld a = (P[(m + kl) % n] - p).cross(P[(m + 1 + kl) % n] - p) * w, b = (P[(m + kl) % n] - p).cross(P[(m - 1 + n + kl) % n] - p) * w;
       if(geq(a, 0) && geq(b, 0)) return m;
       if(geq(a, 0)) r = m - 1, res = m;
       else l = m + 1;
        }
        return res;
    };

auto bs = [&](int l, int r, const vector<point> & A, ld w) -> int {
        int res = l;
        ld w1 = p.x * w;
        while(l <= r){
       int m = (l + r) / 2;
       if(ge(A[m].x * w, w1)) r = m - 1;
       else res = m, l = m + 1;
    }
        return res;
};

point left = p, rigth = p;

int t1 = bs(0, m - 1, Ps[0], 1), t2 = bs(0, k - 1, Ps[1], -1);

auto u1 = tang(0, t1, -1, 0), u2 = tang(0, t2, -1, lk);
auto v1 = tang(t1, m - 1, 1, 0), v2 = tang(t2, k - 1, 1, lk);

if(leq((P[u1] - p).cross(P[(u1 - 1 + n) % n] - p), 0) && leq((P[u1] - p).cross(P[(u1 + 1) % n] - p), 0)) left = P[u1];
if(leq((P[(lk + u2) % n] - p).cross(P[(lk + u2 - 1 + n) % n] - p), 0) && leq((P[(lk + u2) % n] - p).cross(P[(lk + u2 + 1) % n] - p), 0)) left = P[(lk + u2) % n];

if(geq((P[v1] - p).cross(P[(v1 - 1 + n) % n] - p), 0) && geq((P[v1] - p).cross(P[(v1 + 1) % n] - p), 0)) rigth = P[v1];
if(geq((P[(lk + v2) % n] - p).cross(P[(lk - 1 + n + v2) % n] - p), 0) && geq((P[(lk + v2) % n] - p).cross(P[(lk + 1 + v2) % n] - p), 0)) rigth = P[(lk + v2) % n];

return {left, rigth};

Musical recommendation: New Kid in Town ^^