結果

問題 No.325 マンハッタン距離2
ユーザー moti
提出日時 2015-12-19 00:22:07
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0