1279 Art Gallery

問題概要

凸とは限らない多角形が与えられる。
この多角形の内部のうち、全ての辺から見える部分の面積を求めよ。

解法

AOJに全く同じ問題があったような……
全ての辺から見える多角形を求める=一つの辺で見えなくなる部分を次々切っていく

ソースコード

spaghetti sourceの凸多角形の切断、多角形の面積を使用。

int main()
{
  int CS; scanf("%d",&CS);
  rep(cs,CS){
    int n; scanf("%d",&n);
    G g,f;
    rep(i,n){
      int x,y;
      scanf("%d%d",&x,&y);
      g.pb(P(x,y));
    }
    f.pb(P(-100000,-100000)); f.pb(P(100000,-100000));
    f.pb(P(100000,100000)); f.pb(P(-100000,100000));
    rep(i,n){
      f=convex_cut(f,L(g[(i+1)%n],g[i]));
    }
    printf("%.2f\n",area2(f)/2);
  }
  return 0;
}