Submission #517327

#TimeUsernameProblemLanguageResultExecution timeMemory
517327KoDZvijezda (COCI19_zvijezda)C++17
20 / 110
1084 ms4416 KiB
#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;
    }
    int Q;
    std::cin >> Q;
    while (Q--) {
        Point p;
        std::cin >> p.x >> p.y;
        bool f = false;
        for (int i = 0; i < N / 2; ++i) {
            if (cross(P[i + 1] - P[i], p - P[i]) >= 0 and cross(P[(i + N / 2 + 1) % N] - P[i + N / 2], p - P[i + N / 2]) >= 0) {
                f = true;
                break;
            }
        }
        std::cout << (f ? "DA" : "NE") << '\n';
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...