結果
問題 | No.325 マンハッタン距離2 |
ユーザー |
|
提出日時 | 2023-03-14 21:04:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 2,567 bytes |
コンパイル時間 | 1,911 ms |
コンパイル使用メモリ | 182,016 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-18 08:25:22 |
合計ジャッジ時間 | 2,772 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;vector<pair<int,int>> Totsuho(vector<pair<int,int>> &pos){int n=pos.size(),n1,n2;sort(pos.begin(), pos.end());if(pos.empty()) return pos;vector<pair<int,int>> res1={pos[0],pos[1]},res2={pos[0],pos[1]};auto cross=[&](pair<int,int> a,pair<int,int> b){return (long long)a.first*b.second-(long long)a.second*b.first;};auto sub=[&](pair<int,int> a,pair<int,int> b){return make_pair(a.first-b.first,a.second-b.second);};for(int i=2;i<n;i++){n1=res1.size(),n2=res2.size();while(n1>=2&&cross(sub(res1[n1-1],res1[n1-2]),sub(pos[i],res1[n1-1]))<=0){res1.pop_back();n1--;}while(n2>=2&&cross(sub(res2[n2-1],res2[n2-2]),sub(pos[i],res2[n2-1]))>=0){res2.pop_back();n2--;}res1.push_back(pos[i]);res2.push_back(pos[i]);}for (int i=res2.size()-2;i>=1;i--)res1.push_back(res2[i]);return res1;}long long Area(vector<pair<int,int>> &tot){int n = tot.size();long long res = 0,xa,xb,ya,yb,dx,dy;for(int i=0;i<n;i++){tie(xa,ya)=tot[i];tie(xb,yb)=tot[(i+1)%n];res+=(xb-xa)*(yb+ya);}return abs(res);}long long count_edgepoint(vector<pair<int,int>> &tot){int n = tot.size();long long res = n, xa, xb, ya, yb, dx, dy;for(int i=0;i<n;i++){tie(xa, ya) = tot[i];tie(xb, yb) = tot[(i + 1) % n];dx = abs(xa - xb);dy = abs(ya - yb);res += __gcd(dx, dy) - 1;}return res;}int main(){ios::sync_with_stdio(false);cin.tie(0);ll x1, y1, x2, y2, d;cin >> x1 >> y1 >> x2 >> y2 >> d;vector<pair<int,int>> c = {{x1, y1},{x1, y2},{x2, y1},{x2, y2},{d, 0},{-d, 0},{0, d},{0, -d},{x1, d - abs(x1)},{x1, -(d - abs(x1))},{x2, d - abs(x2)},{x2, -(d - abs(x2))},{d - abs(y1), y1},{-(d - abs(y1)), y1},{d - abs(y2), y2},{-(d - abs(y2)), y2}};vector<pair<int,int>> pos;auto f = [&](int x, int y){if(abs(x) + abs(y) <= d && x1 <= x && x <= x2 && y1 <= y && y <= y2){pos.emplace_back(x, y);}};for(auto &&p : c) f(p.first, p.second);auto tot = Totsuho(pos);if(tot.size() <= 1){cout << 0 << '\n';return 0;}cout << (Area(tot) + count_edgepoint(tot) + 2) / 2 << '\n';}