Submission #141331

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
141331	2019-08-07T12:34:04 Z	tutis	Tri (CEOI09_tri)	C++17	100 / 100	654 ms	33472 KB

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 = NULL, *right = NULL;
	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)
			return 0;
		if (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)
		{
			if (left->get(A, B))
				return 1;
			return right->get(A, B);
		}
		return 0;
	}
};
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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	504 KB	Output is correct
2	Correct	6 ms	632 KB	Output is correct
3	Correct	119 ms	6904 KB	Output is correct
4	Correct	219 ms	17396 KB	Output is correct
5	Correct	437 ms	33472 KB	Output is correct
6	Correct	484 ms	17912 KB	Output is correct
7	Correct	620 ms	22224 KB	Output is correct
8	Correct	517 ms	22816 KB	Output is correct
9	Correct	573 ms	24584 KB	Output is correct
10	Correct	654 ms	26580 KB	Output is correct