SRM 558 div1 Ear（前缀和预处理+枚举）

傻子题。
枚举两个蓝点然后二分出可行的红点范围。
再加一个前缀和预处理优化一下即可。
时间复杂度$O(n^{2}lo{g}_n)$ 我也不知道为啥原题数据范围是300
代码：

#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const double eps=1e-5;
class Ear{
	public:
	vector<int>a;
	vector<pii>b;
	ll f[605][605];
	int n,m;
	inline ll C2(int x){return x<=0?0:(ll)x*(x-1)/2;}
	inline ll C3(int x){return x<=0?0:(ll)x*(x-1)*(x-2)/6;}
	inline int lower_bound(int x){
		int res=0,l=1,r=n,mid;
		if(x<a[1])return 0;
		if(x>=a[n])return n;
		while(l<=r)(x>=a[mid=l+r>>1])?(l=mid+1,res=mid):(r=mid-1);
		return res;
	}
	inline ll getCount(vector<string>rx,vector<string>bx,vector<string>by){
		string A,B,C;
		for(ri i=0;i<rx.size();++i)A=A+rx[i];
		for(ri i=0;i<bx.size();++i)B=B+bx[i];
		for(ri i=0;i<by.size();++i)C=C+by[i];
		stringstream sa(A),sb(B),sc(C);
		int x,y;
		a.clear(),b.clear();
		while(sa>>x)a.push_back(x);
		while(sb>>x)sc>>y,b.push_back(pii(y,x));
		n=a.size(),m=b.size();
		a.push_back(-1e9),b.push_back(pii(-1e9,-1e9));
		sort(a.begin(),a.end());
		sort(b.begin(),b.end());
		ll ret=0;
		for(ri i=1;i<=n;++i)for(ri j=n;j;--j)f[i][j]=0;
		for(ri i=1;i<=n;++i)for(ri j=n;j;--j)f[i][j]=C2(j-i-1)+f[i-1][j]+f[i][j+1]-f[i-1][j+1];
		ll det;
		double t;
		for(ri x,L,R,M,ql,qr,i=1;i<m;++i){
			for(ri j=i+1;j<=m;++j){
				if(b[i].fi==b[j].fi)continue;
				if(b[i].se==b[j].se){
					x=lower_bound(b[i].se);
					if(x<2||x==n)continue;
					ql=x-(b[i].se==a[x]),qr=x+1;
					det=f[ql][qr];
					int tt=a[x]==b[i].se?x:x+1;
					det-=(ll)ql*C3(n-tt+1);
					tt=x;
					det-=(ll)(n-qr+1)*C3(tt);
				}
				else if(b[i].se<b[j].se){
					t=(double)((ll)b[i].se*b[j].fi-(ll)b[i].fi*b[j].se)/(double)(b[j].fi-b[i].fi);
					x=floor(t);
					L=lower_bound(x);
					R=lower_bound(b[j].se);
					M=lower_bound(b[i].se);
					L+=t-a[L]>=eps;
					if(L<2||R>n-1)continue;
					ql=L-1,qr=R+1;
					det=f[ql][qr];
					int tt=a[M]==b[i].se?M:M+1;
					det-=(ll)ql*(C3(n-tt+1)-C3(R-tt+1));
					tt=M;
					det-=(ll)(n-R)*(C3(tt)-C3(tt-L+1));
				}
				else{
					t=(double)((ll)b[i].se*b[j].fi-(ll)b[i].fi*b[j].se)/(double)(b[j].fi-b[i].fi);
					x=floor(t);
					R=lower_bound(x);
					L=lower_bound(b[j].se);
					M=lower_bound(b[i].se);
					L+=b[j].se!=a[L];
					if(L<2||R>n-1)continue;
					ql=L-1,qr=R+1;
					det=f[ql][qr];
					int tt=a[M]==b[i].se?M:M+1;
					det-=(ll)ql*(C3(n-tt+1)-C3(R-tt+1));
					tt=M;
					det-=(ll)(n-R)*(C3(tt)-C3(tt-L+1));
				}
				ret+=det;
			}
		}
		return ret;
	}
};