제출 #517386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
517386		KoD	Zvijezda (COCI19_zvijezda)	C++17	110 / 110	169 ms	7976 KiB

zvijezda

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using i64 = std::int64_t;
using i128 = __int128_t;

struct Point {
    i64 x, y;
    Point() : x(0), y(0) {}
    Point(const i64 x, const i64 y) : x(x), y(y) {}
    Point operator-(const Point& t) const {
        return Point(x - t.x, y - t.y);
    }
    friend i128 cross(const Point& p, const Point& q) {
        return (i128)p.x * q.y - (i128)p.y * q.x;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T, N;
    std::cin >> T >> N;
    vector<Point> P(N);
    for (auto& [x, y] : P) {
        std::cin >> x >> y;
    }
    P.push_back(P[0]);
    const auto ccw = [&](const int i, const Point& p) {
        return cross(P[i + 1] - P[i], p - P[i]) > 0;
    };
    int Q;
    std::cin >> Q;
    int count = 0;
    const int H = N / 2;
    while (Q--) {
        const Point p = [&] {
            i64 a, b;
            std::cin >> a >> b;
            const i64 x = (i64)T * count * count * count;
            return Point(a ^ x, b ^ x);
        }();
        if (ccw(0, p) and ccw(N / 2, p)) {
            std::cout << "DA\n";
            count += 1;
            continue;
        }
        if (!ccw(0, p) and !ccw(H, p)) {
            std::cout << "NE\n";
            continue;
        }
        const int pivot = (ccw(0, p) ? 0 : H);
        const int other = pivot ^ H;
        int len = 0;
        len += [&] {
            int ok = 0, ng = H;
            while (ng - ok > 1) {
                const int md = (ok + ng) / 2;
                (ccw(pivot + md, p) ? ok : ng) = md;
            }
            return ng;
        }();
        len += [&] {
            int ok = 0, ng = H;
            while (ng - ok > 1) {
                const int md = (ok + ng) / 2;
                (ccw(other + md, p) ? ng : ok) = md;
            }
            return H - ng;
        }();
        if (len > H) {
            std::cout << "DA\n";
            count += 1;
        } else {
            std::cout << "NE\n";
        }
    }
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60