Hatena::Grouptopcoder

not's memo

 | 

2013-07-28

円と多角形の共通部分面積

11:37 | はてなブックマーク - 円と多角形の共通部分面積 - not's memo

※可読性は著しく低いです

※他のライブラリの実装に激しく依存します

D aCTnc(D r, P p1, P p2) {return sig(abs((p1 + p2) / (D)2), r) <= 0 ? det(p1, p2) / 2 : r * r * arg(0, p1, p2) / 2;}
D aCT(D r, P p1, P p2) {
  if (!sig(r) || near(0, p1) || near(0, p2) || near(p1, p2)) return 0;
  pair<P, P> pp = pCL((C){0, r}, (L){p1, p2});
  if ((p1 < pp.first) != (pp.first < p2) && (p1 < pp.second) != (pp.second < p2)) return aCTnc(r, p1, p2);
  return aCTnc(r, p1, pp.first) + aCTnc(r, pp.first, pp.second) + aCTnc(r, pp.second, p2);
}
D aCPol(C c, Pol pol) {D res = 0; rep (i, pol.size()) res += aCT(c.r, pol[i] - c.c, at(pol, i + 1) - c.c); return res;}
 |