#66902 (C++11) No.325 マンハッタン距離2

• 問題: No.325 マンハッタン距離2
• ユーザー: moti
• 提出日時: 2015-12-19 00:22:07
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 2 ms / 1,000 ms
• コード長: 5,574 bytes
• コンパイル時間: 1,361 ms
• コンパイル使用メモリ: 117,696 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-16 08:46:55
• 合計ジャッジ時間: 2,258 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	1 ms; 5,376 KB
testcase_19	AC	1 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	2 ms; 5,376 KB
testcase_23	AC	2 ms; 5,376 KB
testcase_24	AC	1 ms; 5,376 KB
testcase_25	AC	2 ms; 5,376 KB
testcase_26	AC	2 ms; 5,376 KB

ソースコード

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define minimize(a, x) a = std::min(a, x)
#define maximize(a, x) a = std::max(a, x)

typedef long long ll;
int const inf = 1<<29;

typedef long double ld;

const ld EPS = std::numeric_limits<ld>::epsilon();
const ld INF = 1e12;
typedef complex<ld> P;
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
ld cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
ld dot(const P& a, const P& b) {
  return real(conj(a)*b);
}

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

typedef vector<P> G;

struct C {
  P p; ld r;
  C(const P &p, ld r) : p(p), r(r) { }
};

typedef P point;

int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;       // counter clockwise
  if (cross(b, c) < 0)   return -1;       // clockwise
  if (dot(b, c) < 0)     return +2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;       // a--b--c on line
  return 0;
}

bool intersectLL(const L &l, const L &m) {
  return abs(cross(l[1]-l[0], m[1]-m[0])) > EPS || // non-parallel
         abs(cross(l[1]-l[0], m[0]-l[0])) < EPS;   // same line
}
bool intersectLS(const L &l, const L &s) {
  return cross(l[1]-l[0], s[0]-l[0])*       // s[0] is left of l
         cross(l[1]-l[0], s[1]-l[0]) < EPS; // s[1] is right of l
}
bool intersectLP(const L &l, const P &p) {
  return abs(cross(l[1]-p, l[0]-p)) < EPS;
}
bool intersectSS(const L &s, const L &t) {
  return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 &&
         ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;
}
bool intersectSP(const L &s, const P &p) {
  return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS; // triangle inequality
}

// a1,a2を端点とする線分とb1,b2を端点とする線分の交点計算
P intersection_ls(P a1, P a2, P b1, P b2) {
  P b = b2-b1;
  ld d1 = abs(cross(b, a1-b1));
  ld d2 = abs(cross(b, a2-b1));
  ld t = d1 / (d1 + d2);

  return a1 + (a2-a1) * t;
}

P intersection_ls(L const& s1, L const& s2) {
  return intersection_ls(s1[0], s1[1], s2[0], s2[1]);
}

typedef vector<P> polygon;

enum { OUT, ON, IN };
int convex_contains(const polygon &P, const point &p) {
  const int n = P.size();
  point g = (P[0] + P[n/3] + P[2*n/3]) / (ld)3.0; // inner-point
  int a = 0, b = n;
  while (a+1 < b) { // invariant: c is in fan g-P[a]-P[b]
    int c = (a + b) / 2;
    if (cross(P[a]-g, P[c]-g) > 0) { // angle < 180 deg
      if (cross(P[a]-g, p-g) > 0 && cross(P[c]-g, p-g) < 0) b = c;
      else                                                  a = c;
    } else {
      if (cross(P[a]-g, p-g) < 0 && cross(P[c]-g, p-g) > 0) a = c;
      else                                                  b = c;
    }
  }
  b %= n;
  if (cross(P[a] - p, P[b] - p) < 0) return 0;
  if (cross(P[a] - p, P[b] - p) > 0) return 2;
  return 1;
}

typedef ld number;
#define prev(P, i) ( P[(i-1 + P.size()) % P.size()] )
#define curr(P, i) ( P[i % P.size()] )
#define next(P, i) ( P[(i+1) % P.size()] )


vector<point> convex_hull(vector<point> ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end());
  vector<point> ch(2*n);
  for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
    while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper-hull
    while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  ch.resize(k-1);
  return ch;
}

int is_point_on_line(point a, point b, point c) {
  return ( cross(b-a, c-a), 0.0 ) <= EPS;
}

polygon convex_cut(const polygon& P, const L& l) {
  polygon Q;
  for (int i = 0; i < P.size(); ++i) {
    point A = curr(P, i), B = next(P, i);
    if (ccw(l[0], l[1], A) != -1) Q.push_back(A);
    if (ccw(l[0], l[1], A)*ccw(l[0], l[1], B) < 0)
      Q.push_back(intersection_ls(L(A, B), l));
  }
  return Q;
}

polygon convex_and(const polygon& g, const polygon& h) {
  polygon r = g;
  rep(i, h.size()) {
    r = convex_cut(r, L(h[i],h[(i+1)%h.size()]));
  }
  return r;
}

number area2(const polygon& P) {
  number A = 0;
  for (int i = 0; i < P.size(); ++i) 
    A += cross(curr(P, i), next(P, i));
  return A;
}


long long PickGetI(ld S, ld b) {
  return round(S - b / 2.0) + 1;
}

int main() {

  ld x1, y1, x2, y2, d;
  cin >> x1 >> y1 >> x2 >> y2 >> d;

  polygon D;
  D.emplace_back(d, 0);
  D.emplace_back(0, d);
  D.emplace_back(-d, 0);
  D.emplace_back(0, -d);

  polygon R;
  R.emplace_back(x1, y1);
  R.emplace_back(x2, y1);
  R.emplace_back(x2, y2);
  R.emplace_back(x1, y2);

  auto C = convex_and(D, R);

  if(C.empty()) {
    puts("0");
    exit(0);
  }

  ll b = 0;
  rep(i, C.size()) {
    auto& tar = C[(i+1)%C.size()];
    auto& cur = C[i];
    ll A = abs((ll)(tar.real() - cur.real()));
    ll B = abs((ll)(tar.imag() - cur.imag()));
    if(A == 0) {
      b += B;
    }
    else if(B == 0) {
      b += A;
    }
    else {
      b += __gcd(A, B);
    }
  }

  cout << PickGetI(area2(C) / 2, b) + b << endl;

  return 0;
}