網頁

2014年2月1日 星期六

UVa 12537 Radiation


題意:
  在核能廠半徑範圍內的住家可以得到protective equipments,a和c區域可以得到一組,而b區域因為在重疊範圍內,所以有2組,但在範圍外的d區域沒有equipment,但因為equipments只要1組就夠用了,因此b區域的住家可以分給d區域的住家,題目求d區域在b區域給了equipments之後還有幾戶住家沒有equipments,即為(d-b)。
  給定一堆點座標和兩個圓心座標,每次兩個圓都有不同的半徑,題目所求為在圓外面點的數量減掉在左圓且在右圓內點的數量,為(d-b)。

想法:
  • 找出在左圓範圍內點的數量(a+b)
  • 找出在右圓範圍內點的數量(c+b)
  • 所有點的總數N=a+b+c+d
  • 所求即為N-(a+b)-(c+b) = d-b