結果

問題 No.1999 Lattice Teleportation
ユーザー 🍮かんプリン🍮かんプリン
提出日時 2022-07-02 19:30:54
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 8,662 bytes
コンパイル時間 1,364 ms
コンパイル使用メモリ 128,760 KB
実行使用メモリ 12,428 KB
最終ジャッジ日時 2023-08-18 11:25:05
合計ジャッジ時間 4,968 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <limits>
#include <list>
#include <numeric>
#include <queue>
#include <stack>
#include <utility>
#include <array>
#include <random>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#include <chrono>
#include <cstring>
#include <memory>
#include <unistd.h>
using namespace std;
typedef long long ll;
#define dump(x) cerr << #x << " = " << (x) << " [" << __LINE__ << ":" << __FUNCTION__ << "] " << endl
// vector???��?��??��?��o???��?��??��?��???��?��??��?��
template < typename T >
ostream& operator<<(ostream& os, vector< T >& v) {
    os << "{";
    for (int i = 0; i < (int)v.size(); i++) {
        os << v[i] << (i < v.size() - 1 ? ", " : "");
    }
    os << "}";
    return os;
}
// pair???��?��??��?��o???��?��??��?��???��?��??��?��
template < typename T, typename U >
ostream& operator<<(ostream& os, const pair< T, U >& p) {
    return os << "(" << p.first << ", " << p.second << ")";
}
// map???��?��??��?��o???��?��??��?��???��?��??��?��
template < typename T, typename U >
ostream& operator<<(ostream& os, const map< T, U >& map_var) {
    os << "{";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")";
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set ???��?��??��?��o???��?��??��?��???��?��??��?��
template < typename T >
ostream& operator<<(ostream& os, const set< T >& set_var) {
    os << "{";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr;
        ++itr;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// multiset ???��?��??��?��o???��?��??��?��???��?��??��?��
template < typename T >
ostream& operator<<(ostream& os, const multiset< T >& set_var) {
    os << "{";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr;
        ++itr;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
#pragma endregion

/////////////////////////////////////////

template< int MOD >
struct mint {
public:
    unsigned int x;
    mint() : x(0) {}
    mint(long long v) {
        long long w = (long long)(v % (long long)(MOD));
        if (w < 0) w += MOD;
        x = (unsigned int)(w);
    }
    mint(std::string &s) {
        unsigned int z = 0;
        for (int i = 0; i < s.size(); i++) {
            z *= 10;
            z += s[i] - '0';
            z %= MOD;
        }
        x = z;
    }
    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }
    mint& operator+=(const mint &a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint &a) {
        if ((x -= a.x) >= MOD) x += MOD;
        return *this;
    }
    mint& operator*=(const mint &a) {
        unsigned long long z = x;
        z *= a.x;
        x = (unsigned int)(z % MOD);
        return *this;
    }
    mint& operator/=(const mint &a) {return *this = *this * a.inv(); }
    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs.x == rhs.x;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs.x != rhs.x;
    }
    friend std::ostream& operator<<(std::ostream &os, const mint &n) {
        return os << n.x;
    }
    friend std::istream &operator>>(std::istream &is, mint &n) {
        unsigned int x;
        is >> x;
        n = mint(x);
        return is;
    }
    mint inv() const {
        assert(x);
        return pow(MOD-2);
    }
    mint pow(long long n) const {        
        assert(0 <= n);
        mint p = *this, r = 1;
        while (n) {
            if (n & 1) r *= p;
            p *= p;
            n >>= 1;
        }
        return r;
    }
    
    // 存在しない場合0を返す(二乗して確認).
    // O(log^2MOD)
    mint sqrt() const {
        if (this->x < 2) return *this;
        if (this->pow((MOD-1)>>1).x != 1) return mint(0);
        mint b = 1, one = 1;
        while (b.pow((MOD-1) >> 1) == 1) b += one;
        long long m = MOD-1, e = 0;
        while (m % 2 == 0) m >>= 1, e += 1;
        mint x = this->pow((m - 1) >> 1);
        mint y = (*this) * x * x;
        x *= (*this);
        mint z = b.pow(m);
        while (y.x != 1) {
            int j = 0;
            mint t = y;
            while (t != one) j += 1, t *= t;
            z = z.pow(1LL << (e-j-1));
            x *= z; z *= z; y *= z; e = j;
        }
        return x;
    }
};

constexpr int MOD = 1e9 + 7;

using coord_t = ll;

struct Point {
    coord_t x,y;
    Point():x(0),y(0){}
    Point(coord_t x, coord_t y):x(x),y(y){}
    bool operator<(const Point &p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
    friend std::ostream &operator<<(std::ostream &os, const Point &v) {
        return os << "[" << v.x << "," << v.y << "]";
    }
};

struct Vector {
private:
    // https://codeforces.com/blog/entry/72815?#comment-570942
    inline int quad(coord_t x, coord_t y) const {
        return ((x>=0)^(y>=0))|((y>=0)<<1);
    }
public:
    coord_t x,y;
    Vector():x(0),y(0){}
    Vector(coord_t x, coord_t y):x(x),y(y){}
    Vector(const Vector &v):x(v.x),y(v.y){}
    Vector operator-() const { return Vector() - *this; }
    Vector& operator+=(const Vector &v) {
        x += v.x;
        y += v.y;
        return *this;
    }
    Vector& operator-=(const Vector &v) {
        x -= v.x;
        y -= v.y;
        return *this;
    }
    friend Vector operator+(const Vector& lv, const Vector& rv) {
        return Vector(lv) += rv;
    }
    friend Vector operator-(const Vector& lv, const Vector& rv) {
        return Vector(lv) -= rv;
    }
    // (-pi,pi]
    bool operator<(const Vector &v) const {
        return quad(x,y)==quad(v.x,v.y)?x*v.y>y*v.x:quad(x,y)<quad(v.x,v.y);
    }
    friend std::ostream &operator<<(std::ostream &os, const Vector &v) {
        return os << "[" << v.x << "," << v.y << "]";
    }
};

// AB×CD
inline coord_t cross(const Point &A, const Point &B, const Point &C, const Point &D) {
    return (B.x - A.x) * (D.y - C.y) - (B.y - A.y) * (D.x - C.x);
}

// AB×AC
inline coord_t cross(const Point &A, const Point &B, const Point &C) {
    return cross(A,B,A,C);
}

// OA×OB
inline coord_t cross(const Point &A, const Point &B) {
    return cross(Point(0,0),A,B);
}

// A×B
inline coord_t cross(const Vector &A, const Vector &B) {
    return cross(Point(A.x,A.y),Point(B.x,B.y));
}

// 多角形の面積の2倍
// 反時計回りなら正，時計回りなら負となる
mint<MOD> area(const vector<Point> &p) {
    int n = p.size();
    if (n <= 2) return 0;
    mint<MOD> ans = 0;
    for (int i = 0; i < n; i++) {
        ans += cross(p[i],p[(i+1)%n]);
    }
    return ans;
}

// 多角形内の格子点の数え上げ
// (内部,辺上)
pair<mint<MOD>,mint<MOD>> picks_theorem(const vector<Point> &p) {
    int n = p.size();
    mint<MOD> b = 0;
    for (int i = 0; i < n; i++) {
        coord_t dx = abs(p[(i+1)%n].x-p[i].x);
        coord_t dy = abs(p[(i+1)%n].y-p[i].y);
        b += __gcd(dx,dy);
    }
    return {(area(p)-b+2)/2,b};
}

int main() {
    int n;cin >> n;
    vector<Vector> vec(2*n);
    for (int i = 0; i < n; i++) {
        cin >> vec[2*i].x >> vec[2*i].y;
        vec[2*i+1].x = -vec[2*i].x;
        vec[2*i+1].y = -vec[2*i].y;
    }
    sort(vec.begin(), vec.end());
    vector<Point> a;
    Vector now(0,0);
    for (int i = 0; i < 2*n; i++) {
        a.push_back(Point(now.x,now.y));
        now += vec[i];
    }
    auto ans = picks_theorem(a);
    cout << ans.first + ans.second << endl;
    return 0;
}

/////////////////////////////////////////
0