結果

問題 No.1999 Lattice Teleportation
ユーザー 🍮かんプリン🍮かんプリン
提出日時 2022-07-02 20:05:31
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,936 bytes
コンパイル時間 1,784 ms
コンパイル使用メモリ 179,608 KB
実行使用メモリ 11,116 KB
最終ジャッジ日時 2024-11-27 17:05:46
合計ジャッジ時間 5,007 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 2 ms
5,248 KB
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 # 

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2022.07.02 20:05:22
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;


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;
    }
    
    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:
    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;
    }
    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 << "]";
    }
};

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);
}

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

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

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

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;
    for (int i = 0; i < n; i++) {
        coord_t x,y;cin >> x >> y;
        if (x == 0 && y == 0) continue;
        if (y < 0) x=-x,y=-y;
        vec.push_back(Vector(x,y));
    }
    sort(vec.begin(), vec.end());
    vector<Point> a;
    Vector now(0,0);
    for (int i = 0; i < vec.size(); i++) {
        a.push_back(Point(now.x,now.y));
        now += vec[i];
    }
    for (int i = 0; i < vec.size(); 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