제출 #141236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
141236		tutis	Tri (CEOI09_tri)	C++17	30 / 100	2089 ms	65540 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
*/
#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) {}
};
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;
}
int viduj(point x, point a, point b)
{
	if (sgn(cross(a, x)) != sgn(cross(x, b)))
		return 0;
	if (sgn(cross(b - a, x - a)) != sgn(cross(x - a, -a)))
		return 0;
	return 1;
}
struct quad
{
	int x1, x2;
	int y1, y2;
	int kiek = 0;
	quad* A[4] = {NULL, NULL, NULL, NULL};
	quad(int a1 = 0, int a2 = (1 << 30) - 1, int b1 = 0, int b2 = (1 << 30) - 1):
		x1(a1), x2(a2), y1(b1), y2(b2)
	{

	}
	void fix(int x, int y)
	{
		int xm = (x1 + x2) / 2;
		int ym = (y1 + y2) / 2;
		int t = 0;
		if (x > xm)
			t += 2;
		if (y > ym)
			t++;
		if (t == 0 && A[0] == NULL)
			A[0] = new quad(x1, xm, y1, ym);
		if (t == 1 && A[1] == NULL)
			A[1] = new quad(x1, xm, ym + 1, y2);
		if (t == 2 && A[2] == NULL)
			A[2] = new quad(xm + 1, x2, y1, ym);
		if (t == 3 && A[3] == NULL)
			A[3] = new quad(xm + 1, x2, ym + 1, y2);
	}
	void add(int x, int y)
	{
		if (x1 > x || x > x2 || y1 > y || y > y2)
			return;
		kiek++;
		if (x1 == x2)
			return;
		fix(x, y);
		for (int t = 0; t < 4; t++)
			if (A[t])
				A[t]->add(x, y);
	}
	int get(point a, point b)
	{
		if (kiek == 0)
			return 0;
		int s1 = sgn(cross(b - a, point(x1, y1) - a));
		int s2 = sgn(cross(b - a, point(x1, y2) - a));
		int s3 = sgn(cross(b - a, point(x2, y1) - a));
		int s4 = sgn(cross(b - a, point(x2, y2) - a));
		int s5 = sgn(cross(b - a, -a));
		if (s1 == s2 && s2 == s3 && s3 == s4 && s4 == -s5)
			return 0;
		s1 = sgn(cross(b, point(x1, y1)));
		s2 = sgn(cross(b, point(x1, y2)));
		s3 = sgn(cross(b, point(x2, y1)));
		s4 = sgn(cross(b, point(x2, y2)));
		s5 = -sgn(cross(b, a));
		if (s1 == s2 && s2 == s3 && s3 == s4 && s4 == s5)
			return 0;
		s1 = sgn(cross(a, point(x1, y1)));
		s2 = sgn(cross(a, point(x1, y2)));
		s3 = sgn(cross(a, point(x2, y1)));
		s4 = sgn(cross(a, point(x2, y2)));
		s5 = -sgn(cross(a, b));
		if (s1 == s2 && s2 == s3 && s3 == s4 && s4 == s5)
			return 0;
		if (x1 == x2)
			return viduj(point(x1, y1), a, b);
		if (A[0] && A[0]->get(a, b) > 0)
			return 1;
		if (A[1] && A[1]->get(a, b) > 0)
			return 1;
		if (A[2] && A[2]->get(a, b) > 0)
			return 1;
		if (A[3] && A[3]->get(a, b) > 0)
			return 1;
		return 0;
	}
} medis;
int main()
{
	int K, M;
	cin >> K >> M;
	while (K--)
	{
		int x, y;
		cin >> x >> y;
		medis.add(x, y);
	}
	while (M--)
	{
		point A, B;
		cin >> A.x >> A.y >> B.x >> B.y;
		if (medis.get(A, B) > 0)
			cout << "Y\n";
		else
			cout << "N\n";
	}
}

• Subtask 1: 30 / 100