Submission #123193

#	Time	Username	Problem	Language	Result	Execution time	Memory
123193		tmwilliamlin168	Relay (COI16_relay)	C++14	0 / 100	2 ms	504 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) {
		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+1)/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)
				lb=mb;
			else
				rb=mb-1;
		}
		r.ri=lb;
	} else {
		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+1)/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)
				lb=mb;
			else
				rb=mb-1;
		}
		r.ri=lb;
	}
	if(r.li<r.ri)
		r.li+=m;
	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]), re2=re1;
	for(int i=0; i<n; ++i) {
		if(wt(xa[i], ya[i], re1))
			continue;
		ts tr=gts(xa[i], ya[i]);
		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(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=0; i<n; ++i)
		ans+=!wt(xa[i], ya[i], re2);
	cout << ans-1;
}

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