Codeforces #478 Div2 E. Hag's Khashba

とりあえず幾何出して難易度確保するの止めて…。
http://codeforces.com/contest/975/problem/E

問題

２次元座標における凸多角形が与えられる。
この座標系はY軸負の方向に重力がかかっている。
また、この多角形は厚み・重さ均一の素材でできていると考えてよい。
初期状態では、うち２つの点が固定されているため、動かない。

以下のクエリに順次答えよ。

• 固定点２つのうち、指定された片方を外す。その後少し揺らし、図形が重力に従いもう１つの固定点を中心として回転するので、安定するので待つ。その後、指定した別の点をもう１つ固定する。
• 多角形上の指定された点の現在位置を答える。

解法

まず初期図形における重心と、重心から各点の相対的な位置を距離と角度で求めておく。
以後、各クエリにおいて固定した２点と重心の３点の座標を順次更新していけばよい。

凸多角形の重心は、座標の平均値…ではなくあくまで重みの中心を取らなければいけない。
これはN角形を(N-2)個の３角形に分割し、各重心の（面積での）重みづけ平均を取ればよい。

int N,Q;
long double X[10101],Y[10101];
long double A[10101];
long double R[10101];
long double SX=0,SY=0;
long double D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	for(i=1;i<=N;i++) {
		cin>>X[i]>>Y[i];
	}
	
	double SA=0;
	for(i=2;i<N;i++) {
		double px=(X[1]+X[i]+X[i+1])/3.0;
		double py=(Y[1]+Y[i]+Y[i+1])/3.0;
		double a=abs((X[i]-X[1])*(Y[i+1]-Y[1])-(X[i+1]-X[1])*(Y[i]-Y[1]));
		SX+=a*px;
		SY+=a*py;
		SA+=a;
	}
	SX/=SA;
	SY/=SA;
	
	for(i=1;i<=N;i++) {
		R[i]=hypot(X[i]-SX,Y[i]-SY);
		A[i]=atan2(Y[i]-SY,X[i]-SX);
		while(A[i]<A[i-1]) A[i]+=atan(1)*8;
	}
	
	int P[2]={1,2};
	long double PX[2]={X[1],X[2]};
	long double PY[2]={Y[1],Y[2]};
	
	
	while(Q--) {
		cin>>k;
		if(k==1) {
			int f,t;
			cin>>f>>t;
			if(P[0]==f) i=1, P[0]=t;
			else i=0, P[1]=t;
			SX=PX[i];
			SY=PY[i]-R[P[i]];
			D=atan(1)*2-A[P[i]];
			PX[i^1]=SX+R[t]*cos(D+A[t]);
			PY[i^1]=SY+R[t]*sin(D+A[t]);
			
		}
		else {
			cin>>i;
			long double px=SX+R[i]*cos(D+A[i]);
			long double py=SY+R[i]*sin(D+A[i]);
			_P("%.12lf %.12lf\n",(double)px,(double)py);
			
		}
	}
	
}

まとめ

大量にpretest3で落ちてたので、ジャッジミスかと思ってました、すみません…。