SRM470 Div1 Medium(500) DrawingLines

既に引かれている線分同士の交点、既に引かれている線分とこれから引く線分の交点、これから引く線分同士の交点に分けて考える。

既に引かれている線分の本数をmとする。
既に引かれている線分同士の交点数はO(m²)で求められる。
これから引く線分同士の交点数の期待値は、任意の２点から引く線分が交差する確率は0.5なので、(n-m)*(n-m-1)/2*0.5
既に引かれている線分とこれから引く線分の交点数の期待値。
既に引かれているある線分１本について、この線分の始点より左にある未使用の点数をsl、右をsr、終点より左をel、右をerとすると、この線分と交点を作る線分は(sl*er+sr*el)通り考えられる。それぞれの線分が実際に引かれる確率は1/(n-m)。

MemberSRM470 Div1 500 DrawingLines - 徒然とコード書き

え、O(n²|startDot|)って通るの？　n²を見て、即座にチャレンジしてた((((((；ﾟДﾟ))))))

#include <vector>

using namespace std;

class DrawingLines
{
public:
    double countLineCrossings( int n, vector <int> startDot, vector <int> endDot );
};

double DrawingLines::countLineCrossings( int n, vector <int> startDot, vector <int> endDot )
{
    double p = 0;

    int m = (int)startDot.size();

    //  既に引かれている線分同士の交点数
    for ( int i=0; i<m; i++ )
        for ( int j=i+1; j<m; j++ )
            if ( (startDot[i]-startDot[j])*(endDot[i]-endDot[j]) < 0 )
                p += 1;

    //  既に引かれている線分と、これから引く線分の交点数の期待値
    if ( n - m > 0 )
    for ( int i=0; i<m; i++ )
    {
        int sl = startDot[i] - 1;   //  始点より左にある未使用の点数
        int sr = n - startDot[i];   //  始点より右にある未使用の点数
        int el = endDot[i] - 1;     //  終点より左にある未使用の点数
        int er = n - endDot[i];     //  終点より左にある未使用の点数

        for ( int j=0; j<m; j++ )
        {
            if ( startDot[j] < startDot[i] )  sl--;
            if ( startDot[j] > startDot[i] )  sr--;

            if ( endDot[j] < endDot[i] )  el--;
            if ( endDot[j] > endDot[i] )  er--;
        }

        p += (double)(sl*er+sr*el) / (n-m);
    }

    //  これから引く線分同士の交点数の期待値
    p += (double)(n-m) * (n-m-1) / 4;

    return p;
}