結果

問題 No.325 マンハッタン距離2
ユーザー pekempey
提出日時 2015-12-18 01:09:56
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 4,228 bytes
コンパイル時間 1,857 ms
コンパイル使用メモリ 182,552 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-16 08:19:45
合計ジャッジ時間 2,773 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
using namespace std;
typedef long long ll;
typedef __int128_t D;
typedef complex<D> P;
const D eps = 0;
/*/
D abs(D a) {
    if (a < 0) return -a;
    return a;
}
/*/
D dot(P a, P b) {
    return real(conj(a) * b);
}
D cross(P a, P b) {
    return imag(conj(a) * b);
}
bool comp(P a, P b) {
    if (a.real() != b.real()) return a.real() < b.real();
    return a.imag() < b.imag();
}
vector<P> convexfull(vector<P> &ps) {
    int n = ps.size();
    sort(ps.begin(), ps.end(), comp);
    int k = 0;
    vector<P> qs(n * 2);
    for (int i = 0; i < n; i++) {
        while (k > 1 && cross(qs[k - 1] - qs[k - 2], ps[i] - qs[k - 1]) <= 0) k--;
        qs[k++] = ps[i];
    }
    for (int i = n - 2, t = k; i >= 0; i--) {
        while (k > t && cross(qs[k - 1] - qs[k - 2], ps[i] - qs[k - 1]) <= 0) k--;
        qs[k++] = ps[i];
    }
    qs.resize(k - 1);
    return qs;
}
int ccw(P a, P b, P c) {
    b -= a; c -= a;
    if (cross(b, c) > eps) return 1;
    if (cross(b, c) < -eps) return -1;
    if (dot(b, c) < -eps) return 2;
    if (norm(b) < norm(c)) return -2;
    return 0;
}
bool intersectSS(P p1, P p2, P p3, P p4) {
    return ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 &&
    ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0;
}
P intersection(P p1, P p2, P q1, P q2) {
    P base = q2 - q1;
    D d1 = abs(cross(base, p1 - q1));
    D d2 = abs(cross(base, p2 - q1));
    return p1 + (p2 - p1) * d1 / (d1 + d2);
}
bool contains(P p, vector<P> poly) {
    int n = poly.size();
    int count = 0;
    rep (i, n) {
        P d = poly[(i + 1) % n] - poly[i];
        P x = p - poly[i];
        if (cross(d, x) >= 0) count++;
    }
    return count == n;
}
D area2(vector<P> ps) {
    if (ps.size() <= 2) return 0;
    int n = ps.size();
    D res = 0;
    rep (i, n) {
        P p = ps[i];
        P q = ps[(i + 1) % n];
        res += cross(p, q);
    }
    return res;
}
D lattice(P p, P q) {
    D dx = abs(real(p) - real(q));
    D dy = abs(imag(p) - imag(q));
    return __gcd(dx, dy);
}
int main() {
    D x1, y1, x2, y2, d;
    ll x1_, y1_, x2_, y2_, d_;
    cin >> x1_ >> y1_ >> x2_ >> y2_ >> d_;
    x1 = x1_;
    y1 = y1_;
    x2 = x2_;
    y2 = y2_;
    d = d_;
    if (d == 0) {
        if (x1 <= 0 && 0 <= x2 && y1 <= 0 && 0 <= y2) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
        return 0;
    }
    vector<P> ps;
    vector<P> rect;
    rect.push_back(P(x1, y1));
    rect.push_back(P(x2, y1));
    rect.push_back(P(x2, y2));
    rect.push_back(P(x1, y2));
    vector<pair<P, P>> segs;
    segs.emplace_back(P(x1, y1), P(x2, y1));
    segs.emplace_back(P(x2, y1), P(x2, y2));
    segs.emplace_back(P(x2, y2), P(x1, y2));
    segs.emplace_back(P(x1, y2), P(x1, y1));
    vector<pair<P, P>> lines;
    lines.emplace_back(P(d, 0), P(0, d));
    lines.emplace_back(P(0, d), P(-d, 0));
    lines.emplace_back(P(-d, 0), P(0, -d));
    lines.emplace_back(P(0, -d), P(d, 0));
    vector<P> poly;
    poly.push_back(P(d, 0));
    poly.push_back(P(0, d));
    poly.push_back(P(-d, 0));
    poly.push_back(P(0, -d));
    rep (i, rect.size()) {
        if (contains(rect[i], poly)) {
            ps.push_back(rect[i]);
        }
    }
    rep (i, poly.size()) {
        if (contains(poly[i], rect)) {
            ps.push_back(poly[i]);
        }
    }
    rep (i, segs.size()) {
        rep (j, lines.size()) {
            P p1 = segs[i].first;
            P p2 = segs[i].second;
            P q1 = lines[j].first;
            P q2 = lines[j].second;
            if (intersectSS(p1, p2, q1, q2)) {
                ps.emplace_back(intersection(p1, p2, q1, q2));
            }
        }
    }
    if (ps.size() == 0) {
        cout << 0 << endl;
        return 0;
    }
    set<pair<D, D>> st;
    rep (i, ps.size()) {
        st.emplace(real(ps[i]), imag(ps[i]));
    }
    ps.clear();
    for (auto p : st) {
        ps.push_back(P(p.first, p.second));
    }
    ps = convexfull(ps);
    D S = area2(ps);
    D b = 0;
    rep (i, ps.size()) {
        P p = ps[i];
        P q = ps[(i + 1) % ps.size()];
        b += lattice(p, q);
    }
    D inner = (S - b + 2) / 2;
    D ans = inner + b;
    cout << (ll)ans << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0