Submission #1307152

#TimeUsernameProblemLanguageResultExecution timeMemory
1307152Double_SlashDragon 2 (JOI17_dragon2)C++20
100 / 100
2247 ms8404 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using Vec = array<ll, 2>;

Vec operator-(const Vec &a, const Vec &b) { return {a[0] - b[0], a[1] - b[1]}; }

ll operator^(const Vec &a, const Vec &b) { return a[0] * b[1] - b[0] * a[1]; }

int main() {
    int n, m;
    cin >> n >> m;
    vector<Vec> V[m + 1];
    while (n--) {
        Vec u;
        int c;
        cin >> u[0] >> u[1] >> c;
        V[c].push_back(u);
    }
    Vec d, e;
    cin >> d[0] >> d[1] >> e[0] >> e[1];
    int q;
    cin >> q;
    map<pint, int> cache;
    while (q--) {
        int i, j;
        cin >> i >> j;
        if (not cache.count({i, j})) {
            int &ans = cache[{i, j}];
            for (auto &u: V[i]) {
                auto ud = d - u, ue = e - u;
                bool ltr = (ud ^ ue) < 0;
                for (auto &v: V[j]) {
                    auto uv = v - u;
                    ans += ltr ? (ud ^ uv) < 0 and (uv ^ ue) < 0 : (ue ^ uv) < 0 and (uv ^ ud) < 0;
                }
            }
        }
        cout << cache[{i, j}] << endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...