POJ2318 TOYS 題解
2021-03-29 01:56 作者:昵稱不能為空voidf | 我要投稿
題目大意:給你一個從左上角x1,y1右下角x2,y2的盒子,盒子有若干分區(qū),每兩個分區(qū)有一條直線隔開,直線之間保證兩兩不相交且必定與上下邊界有交點,如圖

且這些直線按照x坐標(biāo)順序給出,先給出m個物品降落坐標(biāo),請算出每個分區(qū)中落入的物品數(shù)。
關(guān)鍵點:二分
做法:將每個直線對象存好后,我們可以用重載比較的upper_bound查找代入給定y的直線中哪個位置是第一個大于x的。由直線一般式Ax+By+C=0移項可得x=-(By+C)/A。從而我們可以快速找出物品落入分區(qū)加入計數(shù)。
為什么可以這么做呢?

代入y,相當(dāng)于橫向劃一條線,直線與這條線的交點就是每個分區(qū)的邊界
模板代碼(不支持cpp11的POJ屬實屑)
標(biāo)簽: