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; }