Submission #123215

#	Time	Username	Problem	Language	Result	Execution time	Memory
123215		tmwilliamlin168	Relay (COI16_relay)	C++14	100 / 100	95 ms	9128 KiB

relay

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=1e5;
int n, m, ans;
ll xa[mxN], ya[mxN], xb[2*mxN], yb[2*mxN];

struct ts {
	int li, ri;
	ll lx, ly, rx, ry;
};

ll cp(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
	return (y3-y1)*(x2-x1)-(y2-y1)*(x3-x1);
}

ts gts(ll x, ll y) {
	ts r;
	if(cp(x, y, xb[m-1], yb[m-1], xb[0], yb[0])<0) {
		//cout << x << " " << y << endl;
		int lb=0, rb=m-2;
		while(lb<rb) {
			int mb=(lb+rb+1)/2;
			if(cp(x, y, xb[m-1], yb[m-1], xb[mb], yb[mb])<0&&cp(x, y, xb[mb-1], yb[mb-1], xb[mb], yb[mb])<0)
				lb=mb;
			else
				rb=mb-1;
		}
		r.ri=lb;
		lb=1, rb=m-1;
		while(lb<rb) {
			int mb=(lb+rb)/2;
			if(cp(x, y, xb[mb], yb[mb], xb[0], yb[0])<0&&cp(x, y, xb[mb], yb[mb], xb[mb+1], yb[mb+1])<0)
				rb=mb;
			else
				lb=mb+1;
		}
		r.li=lb;
	} else {
		//cout << "gt " << x << " " << y << endl;
		int lb=0, rb=m-2;
		while(lb<rb) {
			int mb=(lb+rb+1)/2;
			if(cp(x, y, xb[m-1], yb[m-1], xb[mb], yb[mb])>=0&&cp(x, y, xb[mb-1], yb[mb-1], xb[mb], yb[mb])>=0)
				lb=mb;
			else
				rb=mb-1;
		}
		r.li=lb;
		lb=1, rb=m-1;
		while(lb<rb) {
			int mb=(lb+rb)/2;
			if(cp(x, y, xb[mb], yb[mb], xb[0], yb[0])>=0&&cp(x, y, xb[mb], yb[mb], xb[mb+1], yb[mb+1])>=0)
				rb=mb;
			else
				lb=mb+1;
		}
		r.ri=lb;
	}
	r.lx=r.rx=x;
	r.ly=r.ry=y;
	return r;
}

bool wt(ll x, ll y, ts t) {
	return t.li>t.ri&&cp(xb[t.li], yb[t.li], xb[t.ri], yb[t.ri], x, y)>0&&cp(t.lx, t.ly, xb[t.li], yb[t.li], x, y)<0&&cp(t.rx, t.ry, xb[t.ri], yb[t.ri], x, y)>0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for(int i=0; i<n; ++i)
		cin >> xa[i] >> ya[i];
	cin >> m;
	for(int i=0; i<m; ++i)
		cin >> xb[i] >> yb[i];
	memcpy(xb+m, xb, 8*m);
	memcpy(yb+m, yb, 8*m);
	ts re1=gts(xa[0], ya[0]);
	if(re1.li<re1.ri)
		re1.li+=m;
	//cout << re1.li << " " << re1.ri << endl;
	ts re2=re1;
	for(int i=1; i<n; ++i) {
		ts tr=gts(xa[i], ya[i]);
		//cout << tr.li << " " << tr.ri << endl;
		if(cp(xa[0], ya[0], xb[re1.li], yb[re1.li], xa[i], ya[i])>=0) {
			//cout << "l " << i << endl;
			if(tr.li+m<=re1.li)
				tr.li+=m;
			if(tr.li^re2.li?tr.li<re2.li:cp(re2.lx, re2.ly, xb[tr.li], yb[tr.li], tr.lx, tr.ly)>0) {
				re2.li=tr.li;
				re2.lx=tr.lx;
				re2.ly=tr.ly;
			}
		}
		if(cp(xa[0], ya[0], xb[re1.ri], yb[re1.ri], xa[i], ya[i])<=0) {
			//cout << "r " << i << endl;
			if(tr.ri<re1.ri)
				tr.ri+=m;
			if(tr.ri^re2.ri?tr.ri>re2.ri:cp(re2.rx, re2.ry, xb[tr.ri], yb[tr.ri], tr.rx, tr.ry)<0) {
				re2.ri=tr.ri;
				re2.rx=tr.rx;
				re2.ry=tr.ry;
			}
		}
	}
	for(int i=1; i<n; ++i)
		ans+=!wt(xa[i], ya[i], re2);
	cout << ans;
}

• Subtask 1: 18 / 18
• Subtask 2: 19 / 19
• Subtask 3: 20 / 20
• Subtask 4: 43 / 43