[Tutorial] Tangents of a Polygon in O(log n)

Revision en2, by Jose_17, 2025-02-27 22:35:03

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.

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.
Tags geometry, binary search

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en26 English Jose_17 2025-03-03 22:48:56 0 (published)
en25 English Jose_17 2025-03-03 22:47:32 227 Tiny change: 'ambre ^^\nhttps://' -> 'ambre ^^\n\nhttps://'
en24 English Jose_17 2025-03-03 22:24:09 48 Marckess
en23 English Jose_17 2025-03-03 21:25:44 0 Marckess
en22 English Jose_17 2025-03-03 21:23:48 3 Tiny change: ', Enjambre' -> ', Enjambre ^^'
en21 English Jose_17 2025-03-03 11:04:58 160
en20 English Jose_17 2025-03-03 10:57:53 57 Tiny change: '/details> ```cpp\n\n' -> '/details> \n```cpp\n\n'
en19 English Jose_17 2025-03-03 10:43:08 13 Tiny change: '">\n<br>\n#include' -> '">\n<br>\n```cpp\n#include'
en18 English Jose_17 2025-03-03 10:39:45 6 Tiny change: 'tation">\n\n\n#include' -> 'tation">\n<br>\n#include'
en17 English Jose_17 2025-03-03 10:36:15 52
en16 English Jose_17 2025-03-03 10:32:55 254
en15 English Jose_17 2025-03-03 10:29:49 102
en14 English Jose_17 2025-03-03 10:28:20 344
en13 English Jose_17 2025-03-03 10:25:19 2 Tiny change: 'tation">\nvector<p' -> 'tation">\n\nvector<p'
en12 English Jose_17 2025-03-03 10:23:55 10
en11 English Jose_17 2025-03-03 10:23:37 2365
en10 English Jose_17 2025-03-03 08:09:19 179
en9 English Jose_17 2025-03-03 08:03:12 817
en8 English Jose_17 2025-03-01 04:25:17 60
en7 English Jose_17 2025-03-01 04:23:19 4 Tiny change: 'le="width:350px; height:300px;" />\n' -> 'le="width:500px; height:350px;" />\n'
en6 English Jose_17 2025-03-01 04:22:53 196 Tiny change: '\n\n\n$$\n(P_{i} -' -> '\n\n\n$$\n\newline \n(P_{i} -'
en5 English Jose_17 2025-03-01 03:59:13 2 Tiny change: ' zero:\n\n$$\n(P' -> ' zero:\n\n\n$$\n(P'
en4 English Jose_17 2025-03-01 03:58:35 302
en3 English Jose_17 2025-03-01 03:55:45 469
en2 English Jose_17 2025-02-27 22:35:03 153 Tiny change: 'le="width:500px; heigh' -> 'le="width:350px; heigh'
en1 English Jose_17 2025-02-27 22:27:51 820 Initial revision (saved to drafts)