Submission #157960

#	Time	Username	Problem	Language	Result	Execution time	Memory
157960		imyujin	Tri (CEOI09_tri)	C++14	100 / 100	441 ms	33680 KiB

tri

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

typedef long long lint;
typedef pair<int, int> pii;

#define fi first
#define se second
#define pb push_back

const int MAXN = 100010;
const int MX = 1 << 17;

int N, M;
pii dot[MAXN];
pii tri[MAXN][2], p[MAXN];
int qs[MAXN];
vector<int> que[2 * MX];
bool ans[MAXN];
vector<int> ch[2 * MX];

lint cp(pii a, pii b) { return (lint)a.fi * b.se - (lint)a.se * b.fi; }
lint ccw(pii a, pii b, pii c) { return cp(a, b) + cp(b, c) + cp(c, a); }
bool cmp(const pii a, const pii b) { return ccw(pii(0, 0), a, b) > 0; }
int lwb(pii &a) { return lower_bound(dot, dot + N, a, cmp) - dot; }
int upb(pii &a) { return upper_bound(dot, dot + N, a, cmp) - dot; }
pii operator-(pii a, pii b) { return pii(a.fi - b.fi, a.se - b.se); }

void addquery(int idx, int l, int r, int x, int y, int z) {
	if(x <= l && r <= y) que[idx].pb(z);
	else if(l <= y && x <= r) {
		int m = (l + r) / 2;
		addquery(idx * 2, l, m, x, y, z);
		addquery(idx * 2 + 1, m + 1, r, x, y, z);
	}
}

void f(int idx, int l, int r) {
	/*
	printf("f(idx = %d, l = %d, r = %d)\n", idx, l, r);
	printf("que : ");
	for(auto a : que[idx]) printf("%d ", a);
	puts("");
	*/
	if(l == r) ch[idx].push_back(l);
	else {
		int m = (l + r) / 2;
		f(idx * 2, l, m);
		f(idx * 2 + 1, m + 1, r);
		ch[idx].push_back(ch[idx * 2][0]);
		int t = 0;
		for(int i = 0; i < ch[idx * 2].size(); i++) {
			for(; t + 1 < ch[idx * 2 + 1].size(); t++)
				if(ccw(dot[ch[idx * 2 + 1][t]], dot[ch[idx * 2][i]], dot[ch[idx * 2 + 1][t + 1]]) > 0)
					break;
			if(i + 1 == ch[idx * 2].size() || ccw(dot[ch[idx * 2][i]], dot[ch[idx * 2][i + 1]], dot[ch[idx * 2 + 1][t]]) >= 0)
				break;
			ch[idx].push_back(ch[idx * 2][i + 1]);
		}
		for(int i = t; i < ch[idx * 2 + 1].size(); i++)
			ch[idx].push_back(ch[idx * 2 + 1][i]);
		ch[idx * 2].clear();
		ch[idx * 2 + 1].clear();
	}
	int t = 0;
	for(auto a : que[idx]) {
		while(t + 1 < ch[idx].size() && ccw(tri[a][0], dot[ch[idx][t]], tri[a][1]) >= ccw(tri[a][0], dot[ch[idx][t + 1]], tri[a][1]))
			t++;
		ans[a] |= ccw(dot[ch[idx][t]], tri[a][0], tri[a][1]) > 0;
	}
	/*
	printf("ch[%d] : ", idx);
	for(auto a : ch[idx]) printf("%d ", a);
	puts("");
	printf("end f(%d)\n", idx);
	*/
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M;
	for(int i = 0; i < N; i++) cin >> dot[i].fi >> dot[i].se;
	for(int i = 0; i < M; i++) for(int j = 0; j < 2; j++) cin >> tri[i][j].fi >> tri[i][j].se;

	sort(dot, dot + N, cmp);
	int nn = 0;
	for(int i = 0; i < N; i++) {
		int mn = i;
		for(int j = i + 1; j < N && !ccw(pii(0, 0), dot[i], dot[j]); j++)
			if(dot[j].fi < dot[mn].fi) mn = j;
		dot[nn++] = dot[mn];
	}
	N = nn;
	for(int i = 0; i < M; i++) {
		qs[i] = i;
		if(!cmp(tri[i][0], tri[i][1])) swap(tri[i][0], tri[i][1]);
		p[i] = tri[i][1] - tri[i][0];
	}
	sort(qs, qs + M, [&](const int a, const int b) {
			if(p[a].se < 0 && p[b].se >= 0) return true;
			if(p[a].se >= 0 && p[b].se < 0) return false;
			return cmp(p[b], p[a]);
			});
	for(int i = 0; i < M; i++) 
		addquery(1, 0, N - 1, lwb(tri[qs[i]][0]), upb(tri[qs[i]][1]) - 1, qs[i]);
	f(1, 0, N - 1);
	for(int i = 0; i < M; i++) cout << (ans[i] ? "Y" : "N") << "\n";
	return 0;
}

Compilation message (stderr)

tri.cpp: In function 'void f(int, int, int)':
tri.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < ch[idx * 2].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~
tri.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; t + 1 < ch[idx * 2 + 1].size(); t++)
          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:56:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i + 1 == ch[idx * 2].size() || ccw(dot[ch[idx * 2][i]], dot[ch[idx * 2][i + 1]], dot[ch[idx * 2 + 1][t]]) >= 0)
       ~~~~~~^~~~~~~~~~~~~~~~~~~~~
tri.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = t; i < ch[idx * 2 + 1].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(t + 1 < ch[idx].size() && ccw(tri[a][0], dot[ch[idx][t]], tri[a][1]) >= ccw(tri[a][0], dot[ch[idx][t + 1]], tri[a][1]))
         ~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100