SRM470 div1 medium

解けなっかた人が解説しても仕方がないのでぐぐればいいと思うよ。
全探索。

#include <vector>

using namespace std;

class DrawingLines 
{
	public:
		double countLineCrossings(int n, vector <int> startDot, vector <int> endDot) 
		{
			vector<int> ceil(n,-1);
			int m=startDot.size();
			for(int i=0;i<m;i++)
				ceil[startDot[i]-1]=endDot[i]-1;
			double ans=0.0;
			for(int i=0;i<n;i++)
				for(int j=i+1;j<n;j++)
					if(ceil[i]==-1 && ceil[j]==-1)
						ans+=0.5;
					else if(ceil[i]==-1 && ceil[j]!=-1)
					{
						int c=n-ceil[j]-1;
						for(int k=0;k<m;k++)
							if(ceil[j]<endDot[k]-1)
								c--;
						ans+=double(c)/double(n-m);
					}
					else if(ceil[i]!=-1 && ceil[j]==-1)
					{
						int c=ceil[i];
						for(int k=0;k<m;k++)
							if(endDot[k]-1<ceil[i])
								c--;
						ans+=double(c)/double(n-m);
					}
					else
						ans+=(ceil[j]<ceil[i])?1:0;
			return ans;
		}
};