Submission #141321

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
141321	2019-08-07T12:26:22 Z	tutis	Tri (CEOI09_tri)	C++17	100 / 100	1128 ms	36332 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
*/
#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 (int k = i; k <= j; k++)
		{
			X.push_back(A[k]);
			fix(X);
		}
	}
	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 (hi - lo + 1 > 5)
			{
				int x = (lo + hi) / 2;
				int y = x + 1;
				if (cross(B - A, X[x] - A) < cross(B - A, X[y] - A))
					hi = x;
				else
					lo = x + 1;
			}
			for (int i = lo; i <= hi; i++)
			{
				if (cross(B - A, X[i] - A) < 0)
					return 1;
			}
			return 0;
		}
		if (left)
			return left->get(A, B) + right->get(A, B);
		return 0;
	}
};
int main()
{
	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	8 ms	504 KB	Output is correct
2	Correct	8 ms	632 KB	Output is correct
3	Correct	196 ms	8056 KB	Output is correct
4	Correct	362 ms	19740 KB	Output is correct
5	Correct	748 ms	36332 KB	Output is correct
6	Correct	810 ms	20716 KB	Output is correct
7	Correct	1128 ms	25436 KB	Output is correct
8	Correct	952 ms	26204 KB	Output is correct
9	Correct	1029 ms	28432 KB	Output is correct
10	Correct	1110 ms	30556 KB	Output is correct