AOJ 2256: Divide the Cake

上半分の点の集合が変わるのはO(N^2)回ある。2点を通る直線とy軸の交点を列挙すればこの区間を左側で分けられる。
左側がy=tのときの右側が取れる範囲の大きさは1次式で、上半分の点の集合が同じなら同じ式となるはず。
ということは、この領域の中央に代表させてしまってよい。
ということでそれぞれの区間の真ん中について右側が動く範囲を試していくだけでよい。

確かにいい問題だ。そして気づかない。
あと、割る数はwhでもw^2でもなくてh^2です。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
double x[210];
double y[210];
double ABS(double a){return max(a,-a);}
double EPS=1e-9;
double PI=acos(-1.0);
double th[210];
int main(){
	int w,h,a;
	while(scanf("%d%d%d",&w,&h,&a),a){
		for(int i=0;i<2*a;i++)scanf("%lf%lf",x+i,y+i);
		x[2*a]=w;
		y[2*a]=0;
		x[2*a+1]=w;
		y[2*a+1]=h;
		vector<double>v;
		for(int i=0;i<2*a+2;i++)for(int j=i+1;j<2*a+2;j++){
			if(ABS(x[i]-x[j])<EPS)continue;
			double tmp=y[i]-x[i]*(y[i]-y[j])/(x[i]-x[j]);
			if(tmp<0||tmp>h)continue;
			v.push_back(tmp);
		}
		v.push_back(0);
		v.push_back(h);
		std::sort(v.begin(),v.end());
		double ret=0;
		for(int i=0;i<v.size()-1;i++){
			if(v[i+1]-v[i]<EPS)continue;
			double M=(v[i]+v[i+1])/2;
			for(int j=0;j<2*a+2;j++)th[j]=atan2(y[j]-M,x[j]);
			std::sort(th,th+2*a+2);
			if(th[a]<-PI/2+EPS)th[a]+=EPS;
			if(th[a+1]<-PI/2+EPS)th[a+1]+=EPS;
			if(th[a]>PI/2-EPS)th[a]-=EPS;
			if(th[a+1]>PI/2-EPS)th[a+1]-=EPS;
			
			double L=max(0.0,M+w*tan(th[a]));
			double R=min((double)h,M+w*tan(th[a+1]));
			ret+=max(0.0,R-L)*(v[i+1]-v[i]);
		}
		printf("%.12f\n",ret/h/h);
	}
}