結果

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

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef complex<double> P;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

ll d;
ll solve(ll x1,ll y1,ll x2,ll y2){
  assert(x1>=0 && y1>=0 && x2>=0 && y2>=0);
  // if(d<x1+y1)return 0;
  // if(d>=x2+y2)return (x2-x1+1)*(y2-y1+1);
  ll ly = d-x1;
  ll ry = d-x2;
  ll tx = d-y2;
  ll bx = d-y1;
  if(y1<=ly && ly<=y2){
    if(x1<=bx && bx<=x2){
      return (bx-x1+1)*(bx-x1+2)/2;
    }else{
      return (x2-x1+1)*(x2-x1+2)/2 + (x2-x1+1)*(ry-y1);
    }
  }else if(x1<=tx && tx<=x2){
    if(y1<=ry && ry<=y2){
      return (y2-y1+1)*(x2-x1+1)-(y2-ry+1)*(y2-ry)/2;
    }else{
      return (y2-y1+1)*(x2-x1+1)-((y2-y1+1)*(y2-y1)/2 + (y2-y1+1)*(x2-bx));
    }
  }else if(x2+y2<=d){
    return (y2-y1+1)*(x2-x1+1);
  }else{
    return 0;
  }
}

int main(){
  ll x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;
  cin>>d;
  ll ret = 0;
  if(x1<0 && 0<x2 && y1<0 && 0<y2){
    ret += solve(0,0,x2,y2);
    ret += solve(0,1,x2,-y1);
    ret += solve(1,0,-x1,y2);
    ret += solve(1,1,-x1,-y1);
    // ret -= min(-x1,d)+1;
    // ret -= min(x2,d)+1;
    // ret -= min(-y1,d)+1;
    // ret -= min(y2,d)+1;
    // ret += 1;
  }else if(x1<0 && 0<x2){
    if(y1<0){
      y1=-y1; y2=-y2;
      swap(y1,y2);
    }
    ret += solve(1,y1,x2,y2);
    ret += solve(0,y1,-x1,y2);
    // if(y1<=d && d<y2) ret -= (d-y1+1);
    // else if(y1<=d && y2<=d) ret -= (y2-y1+1);
    // ret -= min(y1,d)+1;
    // ret -= min(y2,d)+1;
    // ret += 1;
  }else if(y1<0 && 0<y2){
    if(x1<0){
      x1=-x1; x2=-x2;
      swap(x1,x2);
    }
    ret += solve(x1,1,x2,y2);
    ret += solve(x1,0,x2,-y1);
    // if(x1<=d && d<x2) ret -= (d-x1+1);
    // else if(x1<=d && x2<=d) ret -= (x2-x1+1);
    // ret -= min(x1,d)+1;
    // ret -= min(x2,d)+1;
    // ret += 1;
  }else{
    if(x1<0){
      x1=-x1; x2=-x2;
      swap(x1,x2);
    }
    if(y1<0){
      y1=-y1; y2=-y2;
      swap(y1,y2);
    }
    ret += solve(x1,y1,x2,y2);
  }
  cout << ret << endl;
  //
  return 0;
}
0