結果
問題 | No.325 マンハッタン距離2 |
ユーザー |
![]() |
提出日時 | 2018-12-05 17:33:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,727 bytes |
コンパイル時間 | 2,221 ms |
コンパイル使用メモリ | 192,892 KB |
最終ジャッジ日時 | 2025-01-06 18:19:14 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include<bits/stdc++.h>using namespace std;using Int = long long;template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}//INSERT ABOVE HEREsigned main(){Int ans=0;auto solve=[&](Int x1,Int y1,Int x2,Int y2,Int d){Int xx1=x1,xx2=x2;Int yy1=y1,yy2=y2;chmax(xx1,0);chmax(yy1,0);if(xx2<0||yy2<0) return;if(xx1+yy1>d) return;//cout<<xx1<<" "<<yy1<<":"<<xx2<<" "<<yy2<<endl;if(xx2+yy2<=d){ans+=(xx2-xx1+1)*(yy2-yy1+1);return;}Int x=d-yy1,y=d-xx1;Int a=d-yy2,b=d-xx2;if(x<=xx2&&y<=yy2){assert(x-xx1==y-yy1);ans+=(x-xx1+1 + 1)*(x-xx1+1)/2;return;}if(x<=xx2&&y>yy2){ans+=(x-xx1+1 + a-xx1+1)*(yy2-yy1+1)/2;return;}if(x>xx2&&y<=yy2){ans+=(y-yy1+1 + b-yy1+1)*(xx2-xx1+1)/2;return;}assert(xx2-a==yy2-b);ans+=(xx2-xx1+1)*(yy2-yy1+1);ans-=(xx2-a+1)*(xx2-a)/2;};Int x1,y1,x2,y2,d;cin>>x1>>y1>>x2>>y2>>d;solve( x1, y1, x2, y2,d);//cout<<ans<<endl;solve( x1,-y2, x2,-y1,d);//cout<<ans<<endl;solve(-x2, y1,-x1, y2,d);//cout<<ans<<endl;solve(-x2,-y2,-x1,-y1,d);//cout<<ans<<endl;if(x1<=0&&0<=x2){Int yy1=y1,yy2=y2;chmax(yy1,-d);chmin(yy2,d);ans-=max(yy2-yy1+1,0LL);}//cout<<ans<<endl;if(y1<=0&&0<=y2){Int xx1=x1,xx2=x2;chmax(xx1,-d);chmin(xx2,d);ans-=max(xx2-xx1+1,0LL);}//cout<<ans<<endl;if(x1<=0&&0<=x2&&y1<=0&&0<=y2) ans--;cout<<ans<<endl;return 0;}