제출 #141236

#제출 시각아이디문제언어결과실행 시간메모리
141236tutisTri (CEOI09_tri)C++17
30 / 100
2089 ms65540 KiB
/*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 timeMemoryGrader output
Fetching results...