Submission #135338

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
135338	2019-07-24T03:52:37 Z	윤교준(#3250)	Tri (CEOI09_tri)	C++14	100 / 100	362 ms	26772 KB

tri

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[sz(V)-2])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ll operator * (const pii &a, const pii &b) { return ll(a.first)*b.second - ll(a.second)*b.first; }
ll ccw(const pii &a, const pii &b, const pii &c) { return a*b + b*c + c*a; }

const int MAXN = 100055;
const int MX = 131072;

struct SEG {
	vector<pii> V[MX*2];

	void upd(int x, pii r) { for(x += MX; x; x >>= 1) V[x].eb(r); }
	void precal() {
		for(int i = MX*2; i--;) {
			vector<pii> T;
			for(auto &p : V[i]) {
				for(; 1 < sz(T) && ccw(befv(T), T.back(), p) >= 0; T.pop_back());
				T.eb(p);
			}
			swap(V[i], T);
		}
	}
	ll f(const pii &a, int p, int q) { return ll(a.first)*p + ll(a.second)*q; }
	ll get(int i, int p, int q) {
		if(V[i].empty()) return INFLL;
		ll r = INFLL;
		int s = 0, e = sz(V[i])-1; for(int m; s < e;) {
			m = (s+e) >> 1;
			ll tl = f(V[i][m], p, q), tr = f(V[i][m+1], p, q);
			if(tl >= tr) {
				s = m+1;
				if(tr < r) r = tr;
			} else {
				e = m;
				if(tl < r) r = tl;
			}
		}
		return min(r, f(V[i][s], p, q));
	}
	ll get(int s, int e, int p, int q) {
		ll r = INFLL;
		for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) {
			if(s&1) {
				ll t = get(s, p, q);
				if(t < r) r = t;
				s++;
			}
			if(~e&1) {
				ll t = get(e, p, q);
				if(t < r) r = t;
				e--;
			}
		}
		return r;
	}
} seg;

pii A[MAXN];

int N, Q;

int f(const pii &p) {
	return int(lower_bound(A, A+N, p, [&](const pii &a, const pii &b) {
		return a*b > 0;
	}) - A);
}

void preprocess() {
	sort(A, A+N, [&](const pii &a, const pii &b) {
		const ll dt = a*b;
		return dt ? dt > 0 : a < b;
	});
	vector<pii> V;
	for(int i = 0; i < N; i++) {
		if(!V.empty() && V.back() * A[i] == 0) continue;
		V.eb(A[i]);
	}
	N = sz(V);
	for(int i = 0; i < N; i++) A[i] = V[i];

	for(int i = 0; i < N; i++) seg.upd(i, A[i]);
	seg.precal();
}

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

	cin >> N >> Q;
	for(int i = 0; i < N; i++) cin >> A[i].first >> A[i].second;
	preprocess();

	for(pii a, b; Q--;) {
		cin >> a.first >> a.second >> b.first >> b.second;
		if(a > b) swap(a, b);
		if(a*b == 0) {
			puts("N");
			continue;
		}
		int dx = b.first-a.first, dy = b.second-a.second;
		dy = -dy; swap(dx, dy);

		ll mn = seg.get(f(b), f(a)-1, dx, dy);
		ll my = ll(dx)*a.first + ll(dy)*a.second;
		puts(my < mn ? "N" : "Y");
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	6776 KB	Output is correct
2	Correct	10 ms	6648 KB	Output is correct
3	Correct	66 ms	12784 KB	Output is correct
4	Correct	122 ms	17140 KB	Output is correct
5	Correct	247 ms	26772 KB	Output is correct
6	Correct	278 ms	22636 KB	Output is correct
7	Correct	362 ms	26476 KB	Output is correct
8	Correct	267 ms	22508 KB	Output is correct
9	Correct	307 ms	24428 KB	Output is correct
10	Correct	343 ms	26732 KB	Output is correct