AOJ 2256 Divide the Cake

ケーキの端にイチゴが乗ってる時(sample1)の対処をメモ。
len(Y)は片方を(0,Y)に固定したときに等分できる右側の部分の長さを返す関数。
ただ、(0,Y)にイチゴがあると色々面倒なので+eps,-epsの２つに分けて処理した。
誤差怖かったけど通ったので良かった(小並感)

int W,H,N;
int x[210],y[210];
double len(double Y)
{
    vector<double> v;
    for(int i=0;i<2*N;i++)v.pb(atan2(y[i]-Y,x[i]));
    sort(all(v));
    double low = tan(v[N-1])*(double)W + Y;
    double high = tan(v[N])*(double)W + Y;
    low = max(low,0.0);
    low = min(low,(double)H);
    high = max(high,0.0);
    high = min(high,(double)H);
    return high-low;
}
int main()
{
    while(1)
    {
        scanf("%d %d %d",&W,&H,&N);
        if(W==0&&H==0&&N==0)break;
        for(int i=0;i<N*2;i++)scanf("%d %d",&x[i],&y[i]);
        vector<P> v;
        for(int i=0;i<N*2;i++)v.pb(P(x[i],y[i]));
        v.pb(P(W,0));v.pb(P(W,H));
        vector<double> border;
        for(int i=0;i<v.size();i++)
        {
            for(int j=i+1;j<v.size();j++)
            {
                if(v[i].fi==v[j].fi)continue;
                double res = (double)v[i].sec-(double)v[i].fi*(double)(v[j].sec-v[i].sec)/(double)(v[j].fi-v[i].fi);
                if(0.0<=res&&res<=(double)H)border.pb(res);
            }
        }
        border.pb(0.0);border.pb(H);
        sort(all(border));
        border.erase(unique(all(border)),border.end());
        double ans = 0.0;
        for(int i=0;i<border.size()-1;i++)ans+=(len(border[i]+eps)+len(border[i+1]-eps))/2.0*(border[i+1]-border[i]);
        ans /= (double)H;
        ans /= (double)H;
        printf("%.12f\n",ans);
    }
    return 0;
}