Submission #141339

#	Time	Username	Problem	Language	Result	Execution time	Memory
141339		tutis	Tri (CEOI09_tri)	C++17	100 / 100	627 ms	24268 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
{
	int x, y;
	point() {}
	point(int x, int y): x(x), y(y) {}
	int d()
	{
		return x + y;
	}
};
point operator-(const point &a, const point &b)
{
	return point(a.x - b.x, a.y - b.y);
}
point operator-(const point &b)
{
	return point(-b.x, -b.y);
}
ll cross(const point &a, const point &b)
{
	return ll(a.x) * b.y - ll(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)
		{
			X.erase(X.end() - 2);
			return fix(X);
		}
	}
	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) {
		if (cross(a, b) == 0)
			return a.d() < b.d();
		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