幾何問題
- 概要
- 反転幾何
- テク一覧
- 全ての座標が異なるx,y座標が10^5くらいの場合は、x^2+y^2が同じ座標が144個くらいしかない 問題
- 偏角ソート
- 単純な偏角ソート コドフォでの実装記事（メモ程度に記録しとく）
- 2点間偏角ソート
- ヘロンの公式
- 辺の長さから面積を求める公式 [ヘロンの公式の証明と使用例 | 高校数学の美しい物語](https://mathtrain.jp/heron)
- [Ravi変換 - 数学についていろいろ解説するブログ](https://shakayami-math.hatenablog.com/entry/2019/03/04/022518)
- ravi変換をすることで、少し扱いやすい式に変形可能
- S^2 = xyz(x+y+z)
- 問題
- [No.1143 面積Nの三角形 - yukicoder](https://yukicoder.me/problems/no/1143)
- 最小包含円
- 全ての点を含む円の半径の最小値を求める
- O(N)解法がある？
- Geometric Median
- 2D空間上での中央値
- 全ての頂点とのユークリッド距離の総和が最小となる点のこと
- [Geometric Median - GeeksforGeeks](https://www.geeksforgeeks.org/geometric-median/)
- [algorithm - The point that minimizes the sum of euclidean distances to a set of n points - Stack Overflow](https://stackoverflow.com/questions/57277247/the-point-that-minimizes-the-sum-of-euclidean-distances-to-a-set-of-n-points)
-
- 焼きなまし？
- [Android #18 | CodeChef](https://www.codechef.com/problems/REN2013E)
- この問題の解法は全部焼きなましに見える
- Weiszfeld's algorithm
- SOCP
- なんかちゃんと読んでないけど、general solutionらしい
- 焼きなまし？
-
- 凸包はこっち
問題
- ライブラリ整備に良さそう
- まとまっているもの
- 細かな問題
- CF339 Peter and Snow Blower distanceSP
- JAG Coin Slider distanceSP
- JOI lines - 直線 (Lines) 交点 解説1 解説2
- CC Points Inside A Polygon 三角形の中にある点が含まれているか 解説
- CF462 A Colorful Prospect
- CC Points Inside A Polygon 解法（凸包の任意の二点間の中点は凸包の線上か内部に存在する）
- AGC021 Holes（凸包と3点が成す角）
- JOI 象使い 問題 解説
- RUPC2018 Day2 I Explosion（最小包含円）
- ECR50 Covered Points （intersectSS, crosspoint, intersectSP）
- AOJ ヒバラ海に沈む遺跡 解説（三平方）
- CF532 NN and the Optical Illusion 解説（余弦定理）
- AC 光の反射 (Reflection of Light)
- AOJ Equilateral Triangle
- ABC151 Enclose All 解説 （最小包含円だが、使わなくてもいい）
- 全て原点を左下に持つ長方形の合成
- 結合後の図形は階段のような形となるので、凸性を維持して管理するテクみたいな感じで階段情報を保持しておけば、合成後の長方形を適切に管理可能
- yukicoder No.1074 増殖
- 反転幾何
- 偏角ソート
- 2点間偏角ソート
- 三角形の面積について条件を満たすものうんぬん
- 線分の傾き順に考えていき、各線分からの距離でのソートをうまく保ちながら、他の頂点を保存しておくテクがある
- それでうまくやってる感じがある
- BESTTRI - Editorial
- http://codeforces.com/blog/entry/9660
- http://codeforces.com/contest/1019/problem/D
- http://codeforces.com/contest/1025/problem/F
- Geometric Median
- [Best Position for a Service Centre - LeetCode Contest](https://leetcode.com/contest/weekly-contest-197/problems/best-position-for-a-service-centre/)
- 未解決
