Submission #141317

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
141317	2019-08-07T12:20:31 Z	tutis	Tri (CEOI09_tri)	C++17	90 / 100	2000 ms	33712 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)
		{
			for (point C : X)
				if (cross(B - A, C - 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

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	504 KB	Output is correct
2	Correct	11 ms	632 KB	Output is correct
3	Correct	193 ms	7040 KB	Output is correct
4	Correct	1779 ms	17792 KB	Output is correct
5	Execution timed out	2087 ms	33712 KB	Time limit exceeded
6	Correct	817 ms	18068 KB	Output is correct
7	Correct	1074 ms	22752 KB	Output is correct
8	Correct	872 ms	23412 KB	Output is correct
9	Correct	1127 ms	25532 KB	Output is correct
10	Correct	1095 ms	27772 KB	Output is correct