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

Правка en1, от Jose_17, 2025-02-27 22:27:51

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.

Теги geometry, binary search

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en26 Английский Jose_17 2025-03-03 22:48:56 0 (published)
en25 Английский Jose_17 2025-03-03 22:47:32 227 Tiny change: 'ambre ^^\nhttps://' -> 'ambre ^^\n\nhttps://'
en24 Английский Jose_17 2025-03-03 22:24:09 48 Marckess
en23 Английский Jose_17 2025-03-03 21:25:44 0 Marckess
en22 Английский Jose_17 2025-03-03 21:23:48 3 Tiny change: ', Enjambre' -> ', Enjambre ^^'
en21 Английский Jose_17 2025-03-03 11:04:58 160
en20 Английский Jose_17 2025-03-03 10:57:53 57 Tiny change: '/details> ```cpp\n\n' -> '/details> \n```cpp\n\n'
en19 Английский Jose_17 2025-03-03 10:43:08 13 Tiny change: '">\n<br>\n#include' -> '">\n<br>\n```cpp\n#include'
en18 Английский Jose_17 2025-03-03 10:39:45 6 Tiny change: 'tation">\n\n\n#include' -> 'tation">\n<br>\n#include'
en17 Английский Jose_17 2025-03-03 10:36:15 52
en16 Английский Jose_17 2025-03-03 10:32:55 254
en15 Английский Jose_17 2025-03-03 10:29:49 102
en14 Английский Jose_17 2025-03-03 10:28:20 344
en13 Английский Jose_17 2025-03-03 10:25:19 2 Tiny change: 'tation">\nvector<p' -> 'tation">\n\nvector<p'
en12 Английский Jose_17 2025-03-03 10:23:55 10
en11 Английский Jose_17 2025-03-03 10:23:37 2365
en10 Английский Jose_17 2025-03-03 08:09:19 179
en9 Английский Jose_17 2025-03-03 08:03:12 817
en8 Английский Jose_17 2025-03-01 04:25:17 60
en7 Английский Jose_17 2025-03-01 04:23:19 4 Tiny change: 'le="width:350px; height:300px;" />\n' -> 'le="width:500px; height:350px;" />\n'
en6 Английский 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 Английский Jose_17 2025-03-01 03:59:13 2 Tiny change: ' zero:\n\n$$\n(P' -> ' zero:\n\n\n$$\n(P'
en4 Английский Jose_17 2025-03-01 03:58:35 302
en3 Английский Jose_17 2025-03-01 03:55:45 469
en2 Английский Jose_17 2025-02-27 22:35:03 153 Tiny change: 'le="width:500px; heigh' -> 'le="width:350px; heigh'
en1 Английский Jose_17 2025-02-27 22:27:51 820 Initial revision (saved to drafts)