結果

問題 No.1999 Lattice Teleportation
ユーザー suisensuisen
提出日時 2022-07-10 18:41:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 8,566 bytes
コンパイル時間 1,856 ms
コンパイル使用メモリ 102,636 KB
実行使用メモリ 15,388 KB
最終ジャッジ日時 2023-09-02 01:59:49
合計ジャッジ時間 6,096 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 3 ms
4,384 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,384 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 82 ms
14,952 KB
testcase_13 AC 122 ms
14,980 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 120 ms
14,956 KB
testcase_16 AC 45 ms
9,100 KB
testcase_17 AC 77 ms
14,132 KB
testcase_18 AC 67 ms
13,780 KB
testcase_19 AC 70 ms
15,388 KB
testcase_20 AC 99 ms
14,964 KB
testcase_21 AC 101 ms
14,768 KB
testcase_22 AC 103 ms
14,932 KB
testcase_23 AC 7 ms
4,380 KB
testcase_24 AC 27 ms
8,024 KB
testcase_25 AC 68 ms
13,908 KB
testcase_26 AC 53 ms
9,672 KB
testcase_27 AC 44 ms
9,108 KB
testcase_28 AC 79 ms
14,440 KB
testcase_29 AC 37 ms
8,552 KB
testcase_30 AC 17 ms
5,708 KB
testcase_31 AC 12 ms
4,604 KB
testcase_32 AC 48 ms
9,592 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define PROBLEM "https://yukicoder.me/problems/no/1999"

#include <iostream>

#include <algorithm>
#include <numeric>
#include <vector>

namespace suisen::integral_geometry {
    template <typename PointType, typename MultipliedType = long long>
    std::vector<int> convex_hull(const std::vector<PointType> &points) {
        const int n = points.size();
        std::vector<int> sorted(n);
        std::iota(sorted.begin(), sorted.end(), 0);
        std::sort(sorted.begin(), sorted.end(), [&points](int i, int j) {
            const auto &[xi, yi] = points[i];
            const auto &[xj, yj] = points[j];
            return xi == xj ? yi < yj : xi < xj;
        });
        std::vector<int8_t> used(n, false);
        sorted.resize(2 * n - 1);
        std::copy(sorted.rbegin() + n, sorted.rend(), sorted.begin() + n);
        std::vector<int> res;
        res.reserve(n);
        int first = sorted[0], last = sorted[n - 1];
        auto isp_pos = [](MultipliedType x1, MultipliedType y1, MultipliedType x2, MultipliedType y2) -> bool {
            auto det = x1 * y2 - y1 * x2;
            return det > 0 or (det == 0 and x1 * x2 + y1 * y2 > 0);
        };
        for (int k : sorted) {
            if (k != first and used[k]) continue;
            for (int sz = res.size(); sz >= 2; --sz) {
                int i = res[sz - 2], j = res[sz - 1];
                if (j == last) break;
                const auto &[xi, yi] = points[i];
                const auto &[xj, yj] = points[j];
                const auto &[xk, yk] = points[k];
                auto ab_x = xj - xi, ab_y = yj - yi;
                auto bc_x = xk - xj, bc_y = yk - yj;
                if (isp_pos(ab_x, ab_y, bc_x, bc_y)) break;
                res.pop_back(), used[j] = false;
            }
            if (not used[k]) res.push_back(k);
            used[k] = true;
        }
        return res;
    }
} // namespace suisen::integral_geometry

#include <cmath>

namespace suisen::integral_geometry {
    // return: calculate the number of lattice points in the polygon or on at least one of the edges of it, using Pick's theorem (https://en.wikipedia.org/wiki/Pick%27s_theorem).
    template <typename PointType, typename MultipliedType = long long>
    MultipliedType count_lattice_points(const std::vector<PointType> &polygon) {
        const int n = polygon.size();
        MultipliedType s = 0, b = 0;
        for (int i = 0; i < n; ++i) {
            auto [x1, y1] = polygon[i];
            auto [x2, y2] = polygon[(i + 1) % n];
            s += MultipliedType(x1) * y2 - MultipliedType(y1) * x2;
            b += std::abs(std::gcd(x2 - x1, y2 - y1));
        }
        return (s + 2 + b) / 2;
    }
} // namespace suisen::integral_geometry

#include <cassert>
#include <iostream>
#include <utility>

namespace suisen::integral_geometry {
    using coordinate_t = long long;

    struct Point {
        coordinate_t x, y;
        constexpr Point(coordinate_t x = 0, coordinate_t y = 0) : x(x), y(y) {}

        operator std::pair<coordinate_t, coordinate_t>() const { return std::pair<coordinate_t, coordinate_t> { x, y }; }

        friend Point operator+(const Point& p) { return p; }
        friend Point operator-(const Point& p) { return { -p.x, -p.y }; }

        friend Point operator+(const Point& lhs, const Point& rhs) { return { lhs.x + rhs.x, lhs.y + rhs.y }; }
        friend Point operator-(const Point& lhs, const Point& rhs) { return { lhs.x - rhs.x, lhs.y - rhs.y }; }
        friend Point operator*(const Point& lhs, const Point& rhs) { return { lhs.x * rhs.x - lhs.y * rhs.y, lhs.x * rhs.y + lhs.y * rhs.x }; }

        friend Point& operator+=(Point& lhs, const Point& rhs) { lhs.x += rhs.x, lhs.y += rhs.y; return lhs; }
        friend Point& operator-=(Point& lhs, const Point& rhs) { lhs.x -= rhs.x, lhs.y -= rhs.y; return lhs; }
        friend Point& operator*=(Point& lhs, const Point& rhs) { return lhs = lhs * rhs; }

        friend Point operator+(const Point& p, coordinate_t real) { return { p.x + real, p.y }; }
        friend Point operator-(const Point& p, coordinate_t real) { return { p.x - real, p.y }; }
        friend Point operator*(const Point& p, coordinate_t real) { return { p.x * real, p.y * real }; }
        friend Point operator/(const Point& p, coordinate_t real) { return { p.x / real, p.y / real }; }

        friend Point operator+=(Point& p, coordinate_t real) { p.x += real; return p; }
        friend Point operator-=(Point& p, coordinate_t real) { p.x -= real; return p; }
        friend Point operator*=(Point& p, coordinate_t real) { p.x *= real, p.y *= real; return p; }
        friend Point operator/=(Point& p, coordinate_t real) { p.x /= real, p.y /= real; return p; }

        friend Point operator+(coordinate_t real, const Point& p) { return { real + p.x, p.y }; }
        friend Point operator-(coordinate_t real, const Point& p) { return { real - p.x, -p.y }; }
        friend Point operator*(coordinate_t real, const Point& p) { return { real * p.x, real * p.y }; }

        friend bool operator==(const Point& lhs, const Point& rhs) { return lhs.x == rhs.x and lhs.y == rhs.y; }
        friend bool operator!=(const Point& lhs, const Point& rhs) { return not (lhs == rhs); }

        friend std::istream& operator>>(std::istream& in, Point& p) { return in >> p.x >> p.y; }
        friend std::ostream& operator<<(std::ostream& out, const Point& p) { return out << p.x << ' ' << p.y; }

        template <std::size_t I>
        coordinate_t get() const {
            if constexpr (I == 0) return x;
            else if constexpr (I == 1) return y;
            else assert(false);
        }
        template <std::size_t I>
        coordinate_t& get() {
            if constexpr (I == 0) return x;
            else if constexpr (I == 1) return y;
            else assert(false);
        }
    };
    
    constexpr Point ZERO = { 0, 0 };
    constexpr Point ONE  = { 1, 0 };
    constexpr Point I    = { 0, 1 };

    constexpr auto XY_COMPARATOR         = [](const Point& p, const Point& q) { return p.x == q.x ? p.y < q.y : p.x < q.x; };
    constexpr auto XY_COMPARATOR_GREATER = [](const Point& p, const Point& q) { return p.x == q.x ? p.y > q.y : p.x > q.x; };
    constexpr auto YX_COMPARATOR         = [](const Point& p, const Point& q) { return p.y == q.y ? p.x < q.x : p.y < q.y; };
    constexpr auto YX_COMPARATOR_GREATER = [](const Point& p, const Point& q) { return p.y == q.y ? p.x > q.x : p.y > q.y; };
} // namespace suisen::integral_geometry

namespace std {
    template <>
    struct tuple_size<suisen::integral_geometry::Point> : integral_constant<size_t, 2> {};
    template <size_t I>
    struct tuple_element<I, suisen::integral_geometry::Point> {
        using type = suisen::integral_geometry::coordinate_t;
    };
}

namespace suisen::integral_geometry {
    /**
     * 1. (x < 0, y = 0) -> pi
     * 2. (x = 0, y = 0) -> 0
     * 3. points with same argument -> arbitrary order
     */
    template <typename PointType, typename MultipliedType = long long>
    bool compare_by_atan2(const PointType &p, const PointType &q) {
        const auto &[x1, y1] = p;
        const auto &[x2, y2] = q;
        if ((y1 < 0) xor (y2 < 0)) return y1 < y2;
        if ((x1 < 0) xor (x2 < 0)) return (y1 >= 0) xor (x1 < x2);
        if (x1 == 0 and y1 == 0) return true;
        if (x2 == 0 and y2 == 0) return false;
        return (MultipliedType(y1) * x2 < MultipliedType(y2) * x1);
    }
    template <typename PointType, typename MultipliedType = long long>
    void sort_points_by_argument(std::vector<PointType> &points) {
        std::sort(points.begin(), points.end(), compare_by_atan2<PointType, MultipliedType>);
    }
} // namespace suisen::integral_geometry

using namespace suisen::integral_geometry;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<Point> ps;
    for (int i = 0; i < n; ++i) {
        Point p;
        std::cin >> p;
        if (p.y < 0) p.x = -p.x, p.y = -p.y;
        if (p.x or p.y) ps.push_back(p);
    }
    sort_points_by_argument(ps);

    std::vector<Point> outer{ { 0, 0 } };

    for (int lp = 0; lp < 2; ++lp) {
        Point sum{ 0, 0 };
        for (const Point &p : ps) outer.push_back(sum += p);
        std::reverse(ps.begin(), ps.end());
    }

    std::vector<Point> convex;
    for (int i : convex_hull<Point, __int128_t>(outer)) convex.push_back(outer[i]);

    std::cout << int(count_lattice_points<Point, __int128_t>(convex) % 1000000007) << std::endl;

    return 0;
}
0