CF603D Ruminations on Ruminants

給定n條直線，兩兩不平行，且任意三條直線不經過同一個點，然后求解滿足原點在外接圓上的由三條直線圍成的三角形有多少個。

首先這道題只需要知道Simson theorem就可以做了。
定理內容是三角形外接圓上的點到三角形三邊的射影共線。
逆定理是滿足到三角形三邊射影共線的點在三角形外接圓上。

那么我們只需要求解出原點到每條直線的垂足，然后枚舉一個點，計算出這個點到后面所有點的斜率，然后相同斜率的就可以產生貢獻，相當于統計平面內三點共線的對數，我們可以通過枚舉+排序做到$O(n^2)$

這里有個技巧，就是斜率不存在的點我們將它們的斜率設為INF。

另外還需要特判一下垂足重合的情況，只會出現在直線經過原點的情況，其他時候垂足一定直線就是一定的。

總結

以上是生活随笔為你收集整理的CF603D Ruminations on Ruminants（计算几何/Simson theorem）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。