Submission #955980

#TimeUsernameProblemLanguageResultExecution timeMemory
955980chrisvilchesDragon 2 (JOI17_dragon2)C++14
60 / 100
4080 ms4792 KiB
#include <bits/stdc++.h> using namespace std; using ll = int; ll Bx, By; struct Point { ll x, y; int idx; inline Point operator-(const Point& p) const { return {x - p.x, y - p.y, idx}; } inline Point operator+(const Point& p) const { return {x + p.x, y + p.y, idx}; } inline long long cross(const Point& p) const { return x * (long long)p.y - y * (long long)p.x; } inline bool operator<(const Point& p) const { return to_upper().cross(p.to_upper()) > 0; } inline Point to_upper() const { return above() ? *this : negate(); } inline bool above() const { // TODO: Improve this const Point B{Bx, By, idx}; return B.cross(*this) > 0; } inline Point negate() const { return {-x, -y, idx}; } }; short orientation(const Point& o, const Point& a, const Point& b) { // assert((a - o).cross(b - o) != 0); const long long x = (a - o).cross(b - o); return (x > 0) - (x < 0); } short bit[30'001]; int bit_n = 30'001; void clear(const int n) { memset(bit, 0, sizeof(short) * n); } // TODO: Return should be int, not short. int sum_single(int r) { int ret = 0; for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r]; return ret; } int sum(int l, int r) { return sum_single(r) - sum_single(l - 1); } void add(int idx, const short delta) { for (; idx < bit_n; idx = idx | (idx + 1)) bit[idx] += delta; } unordered_map<int, vector<Point>> order_by_b; bool cmp_by_b(const Point& p, const Point& q) { const bool a1 = p.above(); const bool a2 = q.above(); if (a1 != a2) return a1; return p.cross(q) > 0; } int handle_query(const vector<Point>& points1, const vector<Point>& points2, const vector<Point>& ord_b, const Point& B) { if (points1.empty() || points2.empty()) return 0; bit_n = (int)points2.size(); clear(points2.size()); for (const auto& q : points2) { if (!q.above()) { add(q.idx, 1); } } int total = 0; const auto middle = lower_bound(ord_b.begin(), ord_b.end(), Point{-B.x, -B.y}, cmp_by_b); int j = 0; for (const Point& p : points1) { while (j < (int)points2.size()) { const Point& q = points2[j]; if (!(q < p)) break; add(q.idx, q.above() ? 1 : -1); j++; } Point from_point = p; Point to_point = B + (p - B).negate(); if (!p.above()) swap(from_point, to_point); // total += 1; // continue; const auto it1 = lower_bound(ord_b.begin(), middle, from_point - B, cmp_by_b); const auto it2 = lower_bound(middle, ord_b.end(), to_point - B, cmp_by_b); const int from = it1 - ord_b.begin(); const int to = it2 - ord_b.begin(); total += sum(from, to - 1); } return total; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, M, Q; while (cin >> N >> M) { vector<vector<Point>> tribe_points(M + 1); for (int i = 0; i < N; i++) { Point p; int tribe; cin >> p.x >> p.y >> tribe; tribe_points[tribe].push_back(p); } Point A; cin >> A.x >> A.y; cin >> Bx >> By; cin >> Q; Bx -= A.x; By -= A.y; for (auto& points : tribe_points) { for (auto& p : points) p = p - A; } const Point B{Bx, By, -1}; for (int m = 0; m <= M; m++) { auto& points = tribe_points[m]; for (auto& p : tribe_points.at(m)) p = p - B; sort(points.begin(), points.end(), cmp_by_b); for (int i = 0; i < (int)points.size(); i++) { points[i].idx = i; } order_by_b[m] = tribe_points.at(m); for (auto& p : tribe_points.at(m)) p = p + B; } for (auto& points : tribe_points) { sort(points.begin(), points.end()); } const Point origin{0, 0, -1}; // TODO: Are the fenwick queries actually faster???? DO some experiments // TODO: Set this value more properly, and explain that this doesn't really help // but it's something. (assuming fenwick is ACTUALLY faster) // TODO: Comment that this solution is probably not the intended one. The example // solution is much faster (under a second). const int big_query = N / 2; while (Q--) { int i, j; cin >> i >> j; if (true || (int)tribe_points[j].size() > big_query) { // cerr << tribe_points[j].size() << " > " << big_query << endl; const int ans = handle_query(tribe_points.at(i), tribe_points.at(j), order_by_b.at(j), B); cout << ans << '\n'; } else { int total = 0; for (const Point& p : tribe_points[i]) { for (const Point& q : tribe_points[j]) { if (orientation(origin, B, p) == 1) { if (orientation(B, p, q) == 1 && orientation(p, origin, q) == 1) total++; } else { if (orientation(origin, p, q) == 1 && orientation(p, B, q) == 1) total++; } } } cout << total << '\n'; } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...