Submission #1028764

#TimeUsernameProblemLanguageResultExecution timeMemory
1028764isaachewPortal (BOI24_portal)C++17
0 / 100
1 ms604 KiB
#include <bits/stdc++.h> /* Have a tiling that can be translated by any amount */ long long gcd(long long a,long long b){ while(a!=0&&b!=0){ a%=b; std::swap(a,b); } return a+b; } std::pair<int,int> getmuls(int a,int b){//extended Euclidean algorithm int aina=1,ainb=0,bina=0,binb=1; while(a!=0&&b!=0){ int adb=a/b; aina-=adb*ainb; bina-=adb*binb; a=a%b; if(a==0)break; int bda=b/a; ainb-=bda*aina; binb-=bda*bina; b=b%a; } return {aina+ainb,bina+binb}; } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); int n; std::cin>>n; long long ia,ib; std::cin>>ia>>ib; long long xrep=0,yrep=0,yoff=0; for(int i=1;i<n;i++){ long long a,b; std::cin>>a>>b; a-=ia,b-=ib; std::pair<int,int> nums=getmuls(b,yrep); long long ngcd=nums.first*b+nums.second*yrep; long long nxrep=std::abs((a*yrep-yoff*b)/ngcd); xrep=gcd(xrep,nxrep); yoff=nums.first*a+nums.second*yoff; yrep=ngcd; yoff%=xrep; } long long result=std::abs(xrep*yrep); std::cout<<(result==0?-1:result)<<'\n'; }
#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...