TopCoder SRM 558 Div1 Medium Ear

今回Easyで手こずったのでMediumは時間切れしてしまった…。
550が解けそうだったのに惜しい。

(URLは掲載待ち)

X軸上の点(赤点)と、第１象限の点(青点)がそれぞれ最大300個与えられるので、２個の赤点と１個の青点からなる鋭角三角形を２個つくり、(底辺は共有してよいが)片方がもう片方を内包する組み合わせを答える。

今回入力がややこしいので、そこは地道に連結して頑張る。(これのせいで時間食った)
外側と内側の三角形の青点を選び、その時の赤点の組み合わせを累積すればよいので、計算は青点を２つ選ぶ組み合わせでO(N^2)で済む。

青点を２つ選んだ時の組み合わせは、青点の左側の点の組み合わせ（内側の青点の左側にある赤点ごとに、外側の三角形の左端点候補の数を累積）と右側の点の組み合わせ（内側の青点の右側にある赤点ごとに、外側の三角形の右端点候補の数を累積）を掛け合わせればよい。
内側の青点が、外側の三角形の外に出ないよう注意していけばよい。

class Ear {
	public:
	vector<int> vrx,vbx,vby;
	char str[3000];
	
	long long calc(int P,int Q) {
		long long px,py,qx,qy;
		long long pbl,pbr;
		int pl,pr,i,c;
		int ql, qr;
		long long lc,rc;
		int res,N;
		
		N=vrx.size();
		px=vbx[P];
		qx=vbx[Q];
		py=vby[P];
		qy=vby[Q];
		if(py<=qy) return 0;
		
		if(px<=qx) {
			pbl=px*(py-qy);
			pbr=px*(py-qy) + (qx-px)*(py);
		}
		else {
			pbl=px*(py-qy) + (qx-px)*(py);
			pbr=px*(py-qy);
		}
		
		ql=-1;
		qr=1000;
		pl=-1;
		pr=1000;
		FOR(i,vrx.size()) {
			if(vrx[i]*(py-qy)<pbl) pl=i;
			if(vrx[i]*(py-qy)>pbr && pr==1000) pr=i;
			if(vrx[i]<qx) ql=i;
			if(vrx[i]>qx && qr==1000) qr=i;
		}
		if(pl<0 || pr==1000 || ql<0 || qr==1000) return 0;
		
		lc=rc=0;
		for(i=1;i<=ql;i++) {
			lc += max(min(i,pl+1),0);
		}
		for(i=qr;i<=N-2;i++) {
			rc += max(min(N-i-1,N-pr),0);
		}
		//_P("%d %d %lld %lld '%d %d %d %d\n",P,Q,lc,rc,ql,qr,pl,pr);
		return lc*rc;
		
	}
	
	
	long long getCount(vector <string> redX, vector <string> blueX, vector <string> blueY) {
		string rx,bx,by;
		char* pc;
		int i;
		rx=redX[0];
		bx=blueX[0];
		by=blueY[0];
		for(i=1;i<redX.size();i++) rx += redX[i];
		for(i=1;i<blueX.size();i++) bx += blueX[i];
		for(i=1;i<blueY.size();i++) by += blueY[i];
		
		vrx.clear();
		vbx.clear();
		vby.clear();
		
		strcpy(str,rx.c_str());
		pc = strtok(str," ");
		while(pc) {
			vrx.push_back(atoi(pc));
			pc=strtok(NULL," ");
		}
		
		strcpy(str,bx.c_str());
		pc = strtok(str," ");
		while(pc) {
			vbx.push_back(atoi(pc));
			pc=strtok(NULL," ");
		}
		
		strcpy(str,by.c_str());
		pc = strtok(str," ");
		while(pc) {
			vby.push_back(atoi(pc));
			pc=strtok(NULL," ");
		}
		
		sort(vrx.begin(),vrx.end());
		
		long long res=0,x,y;
		FOR(x,vbx.size()) {
			FOR(y,vbx.size()) {
				res += calc(x,y);
			}
		}
		return res;
	}

};

なお、vrx[i]*(py-qy)<pbl のあたりの処理は、本当は(py-qy)を右辺に持ってきて割る方が良い。
ただ、ここでdouble型を使ったら誤差のせいで１ケース通らなかったので整数で処理。
うーん、これは本番じゃ気づかないな。

まとめ

数え合わせがしっかりできたので良し。
doubleの誤差の件を除けば、アプローチもすぐ取れたしね。
正直Easyよりラクでした。

ただ、doubleの誤差の件は注意しよう。
できるだけ割り算はやめて反対に移項して乗算するべきだな。