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.↵
↵
<img src="/predownloaded/7a/2b/7a2bc71ba65fd9ebcf0df712893bfe96417c8dc6.png" style="width:350px; height:300px;" />↵
↵
#### 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:↵
↵
↵
$$↵
(P_{i} - p) \times (P_{i+1} - p) \leq 0↵
$$↵
↵
$$↵
(P_{i} - p) \times (P_{i-1} - p) \leq 0↵
$$↵
↵
Now, we will analyze the behavior of these signs in the following example. ↵
↵
<img src="/predownloaded/3d/a3/3da30ef20483807a4de4774405c1ed188eb38e35.png" style="width:500px; height:350px;" />↵
↵
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.↵
↵
<img src="/predownloaded/e0/e1/e0e159af9209f41e9d3db96982045bf68c341391.png" style="width:500px; height:350px;" />↵
↵
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.↵
↵
For the right tangent, we will use these conditions:↵
↵
$$↵
(P_{i} - p) \times (P_{i+1} - p) \geq 0↵
$$↵
↵
$$↵
(P_{i} - p) \times (P_{i-1} - p) \geq 0↵
$$↵
↵
↵
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)$.↵
↵
<spoiler summary="Implementation">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
// Holi c:↵
↵
vector<point> tangentsPointPolygon(const vector<point> & P, const vector<vector<point>> & Ps, const point & p){↵
int n = P.size(), m = Ps[0].size(), k = Ps[1].size();↵
↵
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 = l;↵
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};↵
}↵
```cpp↵
</spoiler>↵
↵
Musical recommendation: Visita, Enjambre ^^
↵
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.↵
↵
<img src="/predownloaded/7a/2b/7a2bc71ba65fd9ebcf0df712893bfe96417c8dc6.png" style="width:350px; height:300px;" />↵
↵
#### 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:↵
↵
↵
$$↵
(P_{i} - p) \times (P_{i+1} - p) \leq 0↵
$$↵
↵
$$↵
(P_{i} - p) \times (P_{i-1} - p) \leq 0↵
$$↵
↵
Now, we will analyze the behavior of these signs in the following example. ↵
↵
<img src="/predownloaded/3d/a3/3da30ef20483807a4de4774405c1ed188eb38e35.png" style="width:500px; height:350px;" />↵
↵
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.↵
↵
<img src="/predownloaded/e0/e1/e0e159af9209f41e9d3db96982045bf68c341391.png" style="width:500px; height:350px;" />↵
↵
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.↵
↵
For the right tangent, we will use these conditions:↵
↵
$$↵
(P_{i} - p) \times (P_{i+1} - p) \geq 0↵
$$↵
↵
$$↵
(P_{i} - p) \times (P_{i-1} - p) \geq 0↵
$$↵
↵
↵
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)$.↵
↵
<spoiler summary="Implementation">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
// Holi c:↵
↵
vector<point> tangentsPointPolygon(const vector<point> & P, const vector<vector<point>> & Ps, const point & p){↵
int n = P.size(), m = Ps[0].size(), k = Ps[1].size();↵
↵
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 = l;↵
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};↵
}↵
```cpp↵
</spoiler>↵
↵
Musical recommendation: Visita, Enjambre ^^
