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; }