제출 #1098470

#제출 시각아이디문제언어결과실행 시간메모리
1098470_8_8_Portal (BOI24_portal)C++17
0 / 100
2036 ms604 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 3e5 + 12, MOD = (int)1e9 + 7; int n, x[N], y[N]; ll G = 0; vector<array<ll, 2>> a; array<ll, 2> Gcd(array<ll, 2> c,array<ll, 2> d) { if(!c[0]) { G = gcd(G, c[1]); return d; } if(!d[0]) { G = gcd(G, d[1]); return c; } if(c[0] < d[0]) { swap(c, d); } ll col = c[0] / d[0]; c[0] -= col * 1ll * d[0]; c[1] -= col * 1ll * d[1]; return Gcd(c, d); } void test() { cin >> n; for(int i = 1; i <= n; i++) { cin >> x[i] >> y[i]; } for(int i = 2; i <= n; i++) { if(x[i] == x[i - 1]) { G = gcd(G, y[i] - y[i - 1]); continue; } if(x[i] > x[i - 1]) { a.push_back({x[i] - x[i - 1], y[i] - y[i - 1]}); } else { a.push_back({x[i - 1] - x[i], y[i - 1] - y[i]}); } } while((int)a.size() >= 2) { auto i = a.back(); a.pop_back(); auto j = a.back(); auto k = Gcd(i, j); a.push_back(k); } cout << G * 1ll * (a[0][0]) << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; // cin >> t; while(t--) test(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...