ICPC練習会2011 Problem.E ケーキ分割問題

解説を参考にして書いてみた。
台形の面積を求めるだけ!って所だけみて書いたら、「あれ?いちごがy軸上にあるとき、上底と下底求められないじゃん」ってなった。
中点の長さを求めればいいんだね。小学校レベルの式がでてこない自分orz
あとy2の範囲がケーキの外にでた時の処理で引っかかった。

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;

int main() {
	while(true) {
		int x[300], y[300];
		int w, h, n;
		cin >> w >> h >> n;
		if(w==0 && h==0 && n==0) break;
		for(int i=0;i<2*n;i++) {
			cin >> x[i] >> y[i];
		}

		vd v;
		v.push_back(0);
		v.push_back(h);
		for(int i=0;i<2*n;i++) {
			for(int j=i+1;j<2*n;j++) {
				if(x[i]==x[j]) continue;
				double a = (double)(y[i]-y[j])/(x[i]-x[j]);
				a = y[i] - a * x[i];
				if(0<=a && a<=h) v.push_back(a);
			}
			if(x[i]==w) continue;

			double a;
			a = (double)y[i]/(x[i]-w);
			a = y[i] - a * x[i];
			if(0<=a && a<=h) v.push_back(a);

			a = (double)(y[i]-h)/(x[i]-w);
			a = y[i] - a * x[i];
			if(0<=a && a<=h) v.push_back(a);

		}
		sort(v.begin(), v.end());

		double prob = 0;
		for(int i=1;i<(int)v.size();i++) {
			double yy = (v[i]+v[i-1])/2;
			double a[300];
			for(int j=0;j<2*n;j++) {
				if(x[j]!=0) a[j] = (y[j]-yy)/x[j];
				else a[j] = y[j]>yy ? 1e100 : -1E100;
			}
			sort(a, a+n*2);
			double b = a[n-1]*w+yy;
			double t = a[n]*w+yy;
			if(b<0) b=0;
			if(b>h) b=h;
			if(t<0) t=0;
			if(t>h) t=h;
			prob += (t-b) * (v[i]-v[i-1]);
		}

		prob /= h*h;
		cout << setprecision(11) << setiosflags(ios::fixed) << prob << endl;
	}
	return 0;
}