1.題目相關(guān)
-
標(biāo)簽：
半平面交 - 題目地址：http://www.lydsy.com/JudgeOnline/problem.php?id=1007
- 題目大意：見(jiàn)原題。
2.思路
-
先介紹一個(gè)概念：
2-1 左邊是上凸殼喘垂，右邊是下凸殼 - 這題顯然是要維護(hù)一個(gè)上凸殼。
- 首先把直線按照斜率為第一關(guān)鍵字权均，截距為第二關(guān)鍵字排序。
- 搞一個(gè)以斜率為關(guān)鍵字的單調(diào)棧，單調(diào)棧記錄的就是當(dāng)前的上凸殼搪柑。
- 算出將入棧的直線與top的交點(diǎn) X1 和 top 與 top-1 兩條直線的交點(diǎn) X2世分。
- 若 X1 <= X2 則將 top 彈出编振。
引用
2-1：http://www.cnblogs.com/BLADEVIL/archive/2013/12/12/3470781.html
