# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
141236 | tutis | Tri (CEOI09_tri) | C++17 | 2089 ms | 65540 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*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";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |