Submission #1189175

#TimeUsernameProblemLanguageResultExecution timeMemory
1189175Zbyszek99Portal (BOI24_portal)C++20
40 / 100
14 ms2496 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; pair<pll,pll> get_0_y(pll v0, pll v1) { if(v0.ff < 0) { v0.ff *= -1; v0.ss *= -1; } if(v1.ff < 0) { v1.ff *= -1; v1.ss *= -1; } if(!(v0.ff >= v1.ff)) swap(v0,v1); if(v1.ff == 0) return {v1,v0}; ll ile = v0.ff/v1.ff; v0.ff -= ile*v1.ff; v0.ss -= ile*v1.ss; if(v0.ff == 0) return {v0,v1}; else return get_0_y(v0,v1); } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); int n; cin >> n; ll px, py; cin >> px >> py; vector<pll> vects; rep(i,n-1) { ll x,y; cin >> x >> y; x -= px; y -= py; vects.pb({x,y}); } if(siz(vects) <= 1) { cout << "-1\n"; return 0; } pll v0 = vects[0]; pll v1 = vects[1]; pair<pll,pll> new_v = get_0_y(v0,v1); v0 = new_v.ff; v1 = new_v.ss; rep2(i,2,n-2) { new_v = get_0_y(v1,vects[i]); v1 = new_v.ss; v0.ss = __gcd(v0.ss,new_v.ff.ss); } if(v0.ff * v1.ss == v1.ff * v0.ss) { cout << "-1\n"; } else { cout << abs(v0.ff * v1.ss - v1.ff * v0.ss) << "\n"; } 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...