Submission #141337

#	Time	Username	Problem	Language	Result	Execution time	Memory
141337		tutis	Tri (CEOI09_tri)	C++17	100 / 100	703 ms	33496 KiB

tri

/*input
4 3
1 2
1 3
5 1
5 3
1 4 3 3
2 2 4 1
4 4 6 3
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point
{
	ll x, y;
	point() {}
	point(ll x, ll y): x(x), y(y) {}
	int d()
	{
		return x + y;
	}
};
point operator-(point a, point b)
{
	return point(a.x - b.x, a.y - b.y);
}
point operator-(point b)
{
	return point(-b.x, -b.y);
}
ll cross(point a, point b)
{
	return a.x * b.y - a.y * b.x;
}
int sgn(ll x)
{
	if (x < 0)
		return -1;
	if (x > 0)
		return 1;
	return 0;
}
void fix(vector<point>& X)
{
	if (X.size() >= 2)
	{
		if (cross(X.back(), X[X.size() - 2]) == 0)
		{
			if (X.back().d() < X[X.size() - 2].d())
			{
				X.erase(X.end() - 2);
				return fix(X);
			}
			else
			{
				X.erase(--X.end());
				return;
			}
		}
	}
	if (X.size() >= 3)
	{
		if (cross(X[X.size() - 1] - X[X.size() - 2], X[X.size() - 2] - X[X.size() - 3]) >= 0)
		{
			X.erase(X.end() - 2);
			return fix(X);
		}
	}
}
struct DS
{
	DS *left, *right;
	vector<point>X;
	DS(point A[], int i, int j)
	{
		if (i < j)
		{
			left = new DS(A, i, (i + j) / 2);
			right = new DS(A, (i + j) / 2 + 1, j);
			for (point c : left->X)
			{
				X.push_back(c);
				fix(X);
			}
			for (point c : right->X)
			{
				X.push_back(c);
				fix(X);
			}
		}
		else
		{
			X = {A[i]};
		}
	}
	int get(point A, point B)
	{
		if (cross(B, X[0]) <= 0 || cross(X.back(), A) <= 0)
			return 0;
		if (cross(A, X[0]) <= 0 && cross(X.back(), B) <= 0)
		{
			int lo = 0;
			int hi = X.size() - 1;
			while (lo < hi)
			{
				int x = (lo + hi) / 2;
				int y = x + 1;
				ll C1 = cross(B - A, X[x] - A);
				ll C2 = cross(B - A, X[y] - A);
				if (C1 < 0 || C2 < 0)
					return 1;
				if (C1 < C2)
					hi = x;
				else
					lo = x + 1;
			}
			if (cross(B - A, X[lo] - A) < 0)
				return 1;
			return 0;
		}
		if (left->get(A, B))
			return 1;
		return right->get(A, B);
	}
};
int main()
{
	ios_base::sync_with_stdio(false);
	int K, M;
	cin >> K >> M;
	point A[K];
	for (point &i : A)
		cin >> i.x >> i.y;
	sort(A, A + K, [&](point a, point b) {return cross(a, b) < 0;});
	DS medis(A, 0, K - 1);
	while (M--)
	{
		point A, B;
		cin >> A.x >> A.y >> B.x >> B.y;
		if (cross(A, B) > 0)
			swap(A, B);
		if (medis.get(A, B) > 0)
			cout << "Y\n";
		else
			cout << "N\n";
	}
}

• Subtask 1: 100 / 100