test/geometry/segment_intersection.test.cpp

View this file on GitHub
Last update: 2024-02-25 23:03:04+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_6_A

Depends on

Code

#define PROBLEM \
    "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_6_A"

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>

#include "data_structure/compress.hpp"
#include "data_structure/fenwick_tree.hpp"

namespace ebi {

using i64 = std::int64_t;

void main_() {
    int n;
    std::cin >> n;
    std::map<i64, std::vector<std::pair<i64, i64>>> xmap, ymap;
    compress<i64> cp;
    std::vector<i64> ret;
    for (int i = 0; i < n; i++) {
        i64 x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        ret.emplace_back(x1);
        ret.emplace_back(x2 + 1);
        cp.add(y1);
        cp.add(y2);
        if (x1 == x2) {
            if (y1 > y2) std::swap(y1, y2);
            xmap[x1].emplace_back(y1, y2);
        } else {
            assert(y1 == y2);
            if (x1 > x2) std::swap(x1, x2);
            ymap[x1].emplace_back(y1, 1);
            ymap[x2 + 1].emplace_back(y1, -1);
        }
    }
    cp.build();
    std::sort(ret.begin(), ret.end());
    ret.erase(std::unique(ret.begin(), ret.end()), ret.end());
    fenwick_tree<i64> fw(cp.size());
    i64 ans = 0;
    for (auto x : ret) {
        for (auto [y, val] : ymap[x]) {
            fw.add(cp.get(y), val);
        }
        for (auto [low, high] : xmap[x]) {
            ans += fw.sum(cp.get(low), cp.get(high + 1));
        }
    }
    std::cout << ans << '\n';
}

}  // namespace ebi

int main() {
    std::cout << std::fixed << std::setprecision(15);
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ebi::main_();
}

#line 1 "test/geometry/segment_intersection.test.cpp"
#define PROBLEM \
    "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_6_A"

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>

#line 2 "data_structure/compress.hpp"

#line 6 "data_structure/compress.hpp"

namespace ebi {

template <class T> struct compress {
  private:
    std::vector<T> cp;

  public:
    compress() = default;

    compress(std::vector<T> cp_) : cp(cp_) {
        build();
    }

    void build() {
        std::sort(cp.begin(), cp.end());
        cp.erase(std::unique(cp.begin(), cp.end()), cp.end());
    }

    void add(const T &val) {
        cp.emplace_back(val);
    }

    int get(const T &val) const {
        return std::lower_bound(cp.begin(), cp.end(), val) - cp.begin();
    }

    int size() const {
        return cp.size();
    }

    bool find(const T &val) const {
        auto itr = std::lower_bound(cp.begin(), cp.end(), val);
        if (itr == cp.end())
            return false;
        else
            return *itr == val;
    }

    T val(int idx) const {
        assert(0 <= idx && idx < (int)cp.size());
        return cp[idx];
    }
};

}  // namespace ebi
#line 2 "data_structure/fenwick_tree.hpp"

#line 5 "data_structure/fenwick_tree.hpp"

namespace ebi {

template <class T> struct fenwick_tree {
  private:
    int n;
    std::vector<T> data;

  public:
    fenwick_tree(int _n) : n(_n), data(std::vector<T>(_n + 1, T(0))) {}

    void add(int i, T val) {
        i++;
        for (int x = i; x <= n; x += x & -x) {
            data[x] += val;
        }
    }

    T prefix_sum(int i) const {
        assert(0 <= i && i <= n);
        T ret = 0;
        for (int x = i; x > 0; x -= x & -x) {
            ret += data[x];
        }
        return ret;
    }

    T sum(int l, int r) const {
        return prefix_sum(r) - prefix_sum(l);
    }

    T all_sum() const {
        return prefix_sum(n);
    }

    // prefix_sum(x) >= key となる最小のxを返す関数 O(log N)

    int lower_bound(T key) {
        if (key <= 0) return 0;
        int x = 0;
        int max = 1;
        while ((max << 1) <= n) max <<= 1;
        for (int k = max; k > 0; k >>= 1) {
            if (x + k <= n && data[x + k] < key) {
                x += k;
                key -= data[x];
            }
        }
        return x + 1;
    }
};

}  // namespace ebi
#line 14 "test/geometry/segment_intersection.test.cpp"

namespace ebi {

using i64 = std::int64_t;

void main_() {
    int n;
    std::cin >> n;
    std::map<i64, std::vector<std::pair<i64, i64>>> xmap, ymap;
    compress<i64> cp;
    std::vector<i64> ret;
    for (int i = 0; i < n; i++) {
        i64 x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        ret.emplace_back(x1);
        ret.emplace_back(x2 + 1);
        cp.add(y1);
        cp.add(y2);
        if (x1 == x2) {
            if (y1 > y2) std::swap(y1, y2);
            xmap[x1].emplace_back(y1, y2);
        } else {
            assert(y1 == y2);
            if (x1 > x2) std::swap(x1, x2);
            ymap[x1].emplace_back(y1, 1);
            ymap[x2 + 1].emplace_back(y1, -1);
        }
    }
    cp.build();
    std::sort(ret.begin(), ret.end());
    ret.erase(std::unique(ret.begin(), ret.end()), ret.end());
    fenwick_tree<i64> fw(cp.size());
    i64 ans = 0;
    for (auto x : ret) {
        for (auto [y, val] : ymap[x]) {
            fw.add(cp.get(y), val);
        }
        for (auto [low, high] : xmap[x]) {
            ans += fw.sum(cp.get(low), cp.get(high + 1));
        }
    }
    std::cout << ans << '\n';
}

}  // namespace ebi

int main() {
    std::cout << std::fixed << std::setprecision(15);
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ebi::main_();
}