ICPC2014Final C Crane Balancing
問題 これを参照 http://icpc.baylor.edu/xwiki/wiki/public/download/worldfinals/problems/icpc2014.pdf
数値積分をやったところもあるみたいですが、しなくても重心は計算できます
三角形の面積を向きづけて考えると(外積でよい)多角形が左回りに頂点P1,...Pnを持つとすると、適当(てきとー)に原点OをとってOPiPi+1たちをi=1~nについて考え、向き付け三角形を重ねあわせる(正の向きなら三角形内に+1,負の向きなら-1)と、全体としては多角形内は+1,外は0になる.これを利用すれば面積も求められるし、重み付きの重心を取ることで重心の位置もわかる
以下コード。入力が必ず正の向きで与えられると思っていたり誤差だったりで死にまくった、結局doubleを使わない方針で.dsが向き付け三角形の面積,Sが多角形の面積,g/Sが重心のx座標.S2とかg6とかの数字は係数
#include <iostream> #include <cstdio> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() typedef long long ll; double eps=1e-11; int main(){ int n; scanf("%d",&n); ll x[100],y[100],S2=0,g6=0,mnx=2001,mxx=-2001; rep(i,n) scanf("%lld%lld",&x[i],&y[i]); rep(i,n){ if(y[i]==0) mnx=min(mnx,x[i]),mxx=max(mxx,x[i]); ll ds2=(x[i]*y[(i+1)%n]-x[(i+1)%n]*y[i]); S2+=ds2; g6+=(x[i]+x[(i+1)%n])*ds2; } if(S2<=0){ S2=-S2; g6=-g6; } ll ub=1e+18,lb=0; if(x[0]<mxx && mxx*S2*3<g6) lb=(g6-mxx*S2*3)/(6*(mxx-x[0])); if(x[0]>=mxx && mxx*S2*3<g6){ printf("unstable\n"); return 0; } if(x[0]>mxx && mxx*S2*3>=g6) ub=(mxx*S2*3-g6+6*(x[0]-mxx)-1)/(6*(x[0]-mxx)); if(x[0]<mnx && mnx*S2*3<=g6) ub=min(ub,(g6-mnx*S2*3+(6*(mnx-x[0]))-1)/(6*(mnx-x[0]))); if(x[0]<=mnx && mnx*S2*3>g6){ printf("unstable\n"); return 0; } if(x[0]>mnx && mnx*S2*3>g6) lb=max(lb,(mnx*S2*3-g6)/(6*(x[0]-mnx))); if(ub==1e+18){ printf("%lld .. inf\n",lb); return 0; } printf("%lld .. %lld\n",lb,ub); return 0; }