読者です 読者をやめる 読者になる 読者になる

Gravity Point (AOJ2626)

わりとすぐ解法がわかり,実装方針も適切なものを選び,実装もすぐ終わったのにccwを写し間違えてたからデバグに40分かかりました.変えたらそっから変更無しでACしたので実質バグ埋めてないしすごくない?(すごくない,写経ぐらいちゃんとしろ)

とりあえずA,B,Xを全部まとめる.x座標が[X,X+1]に入る という不等式が(ma,mbを変数として)一次式でかける.なのでma,mbを変数とした二次元平面で,[ma1,ma2]*[mb1,mb2]と上記の不等式をみたす図形のcapをとればよく,convexcutをかけばOK.
いやほんとひどいミスだ.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef double D;
typedef complex<D> P;
typedef pair<P,P> L;
typedef vector<P> Pol;
D eps=1e-9;
bool eq(D a,D b){return abs(a-b)<eps;}
int sig(D a){return eq(a,0)?0:(a>0?1:-1);}
void fix(D &x){if(sig(x)==0) x=0;}
D cro(P a,P b){return imag(conj(a)*b);}
int ccw(P a,P b,P c){
	if(sig(cro(b-a,c-a))==1) return 1;
	if(sig(cro(b-a,c-a))==-1) return -1;
	if(eq(abs(a-c)+abs(c-b),abs(a-b))) return 0;
	if(eq(abs(a-b)+abs(c-b),abs(a-c))) return -2;
	return 2;
}
D aPol(Pol p){
	int N=p.size();
	D ret=0;
	rep(i,N) ret+=cro(p[i],p[(i+1)%N])/2;
	return ret;
}
bool iLSex(L l,L s){
	return sig(cro(l.sc-l.fs,s.fs-l.fs)*cro(l.sc-l.fs,s.sc-l.fs))<0;
}
P intLL(L a,L b){
	D t=cro(a.sc-a.fs,a.sc-b.fs)/cro(a.sc-a.fs,b.sc-b.fs);
	return b.fs+t*(b.sc-b.fs);
}
Pol convexcut(Pol p,L l){
	Pol ret;
	int N=p.size();
	rep(i,N){
		if(ccw(l.fs,l.sc,p[i])!=-1) ret.pb(p[i]);
		L s=L(p[i],p[(i+1)%N]);
		if(iLSex(l,s)) ret.pb(intLL(l,s));
	}
	return ret;
}
int H,W;
D la,ra,lb,rb,mx;
string s[50];
int main(){
	cin>>H>>W>>la>>ra>>lb>>rb>>mx;
	rep(i,H) cin>>s[i];
	int ca=0,cb=0,cx=0;
	D xa=0,xb=0,xx=0,ya=0,yb=0,yx=0;
	rep(i,H) rep(j,W){
		if(s[i][j]=='A'){
			xa+=j+0.5,ya+=i+0.5,ca++;
		}else if(s[i][j]=='B'){
			xb+=j+0.5,yb+=i+0.5,cb++;
		}else if(s[i][j]=='X'){
			xx+=j+0.5,yx+=i+0.5,cx++;
		}
	}
	xa/=ca,ya/=ca,xb/=cb,yb/=cb,xx/=cx,yx/=cx;
	mx*=cx;
	la*=ca,ra*=ca,lb*=cb,rb*=cb;
	D ans=0;
	rep(ii,H) rep(jj,W){
		D x=jj,y=ii;
		Pol pol;
		pol.pb(P(la,lb));
		pol.pb(P(ra,lb));
		pol.pb(P(ra,rb));
		pol.pb(P(la,rb));
		{
			D A=xa-x,B=xb-x,C=(xx-x)*mx;
			fix(A),fix(B),fix(C);
			if(B!=0){
				P p(0,-C/B),q(1,-(C+A)/B);
				if(B<0) swap(p,q);
				pol=convexcut(pol,L(p,q));
			}else if(A!=0){
				P p(-C/A,0),q(-C/A,1);
				if(A>0) swap(p,q);
				pol=convexcut(pol,L(p,q));
			}else{
				if(C<0) pol.clear();
			}
		}
		{
			D A=xa-x-1,B=xb-x-1,C=(xx-x-1)*mx;
			fix(A),fix(B),fix(C);
			if(B!=0){
				P p(0,-C/B),q(1,-(C+A)/B);
				if(B>0) swap(p,q);
				pol=convexcut(pol,L(p,q));
			}else if(A!=0){
				P p(-C/A,0),q(-C/A,1);
				if(A<0) swap(p,q);
				pol=convexcut(pol,L(p,q));
			}else{
				if(C>0) pol.clear();
			}
		}
		{
			D A=ya-y,B=yb-y,C=(yx-y)*mx;
			fix(A),fix(B),fix(C);
			if(B!=0){
				P p(0,-C/B),q(1,-(C+A)/B);
				if(B<0) swap(p,q);
				pol=convexcut(pol,L(p,q));
			}else if(A!=0){
				P p(-C/A,0),q(-C/A,1);
				if(A>0) swap(p,q);
				pol=convexcut(pol,L(p,q));
			}else{
				if(C<0) pol.clear();
			}
		}
		{
			D A=ya-y-1,B=yb-y-1,C=(yx-y-1)*mx;
			fix(A),fix(B),fix(C);
			if(B!=0){
				P p(0,-C/B),q(1,-(C+A)/B);
				if(B>0) swap(p,q);
				pol=convexcut(pol,L(p,q));
			}else if(A!=0){
				P p(-C/A,0),q(-C/A,1);
				if(A<0) swap(p,q);
				pol=convexcut(pol,L(p,q));
			}else{
				if(C>0) pol.clear();
			}
		}
		if(s[ii][jj]!='.') ans+=(aPol(pol)/(ra-la)/(rb-lb));
	}
	printf("%.12f\n",ans);
}