Submission #1179176

#TimeUsernameProblemLanguageResultExecution timeMemory
1179176razivoPortal (BOI24_portal)C++20
21 / 100
42 ms7240 KiB
#include <iostream> #include <vector> using namespace std; typedef pair<long long, long long> pt; long long d(pt a, pt b) { return a.first*b.first+a.second*b.second; } long long det(pt a,pt b) { return a.first*b.second-a.second*b.first; } long long di(long long a, long long b) { if(a>0) return a/b; if(a==0) return 0; a = -a; if(a%b==0) return -(a/b); else return -(a/b) - 1; } int k = 0; pt mod(pt a,pt b, pt c) { if(a.first<0) {a.first*=-1; a.second*=-1;} if(b.second<0) {b.first*=-1; b.second*=-1;} long long multb = di(d(b,c),(b.first*b.first+b.second*b.second)); long long multa = di(d(a,c),(a.first*a.first+a.second*a.second)); return {c.first-b.first*multb-a.first*multa,c.second-b.second*multb-a.second*multa}; } pt d1red(pt a,pt b) { if(a.first<0) {a.first*=-1; a.second*=-1;} if(b.first<0) {b.first*=-1; b.second*=-1;} pt p = {0,0}; long long mult = di(d(a,b),(a.first*a.first+a.second*a.second)); b = {b.first-a.first*mult,b.second-a.second*mult}; if(b==a) return a; if(b==p) return a; return d1red(b,a); } pair<pt,pt> reduce(pt a, pt b, pt c) { k++; if(k>50000) return {a,c}; if(a.first<0) {a.first*=-1; a.second*=-1;} if(b.first<0) {b.first*=-1; b.second*=-1;} pt p = {0,0}; if(a==p ||b==p||c==p) exit(1); if(det(a,b)==0) { k=0; return { d1red(a,b),c}; } c = mod(a,b,c); if(c==a) return {c,b}; else if(c==b) return {c,a}; if(c == p) return {a,b}; return reduce(b,c,a); } int main() { int n; cin>>n; if(n<3) { cout<<-1<<endl; return 0; } pt prev; cin>>prev.first>>prev.second; vector<pt> t(n-1); for (int i = 0; i < n-1; ++i) { int x,y; cin>>x>>y; t[i] = {prev.first-x,prev.second-y}; prev = {x,y}; } pair<pt,pt> res = {t[0],t[1]}; for (int i = 0; i < n-3; ++i) { k=0; res = reduce(res.first,res.second,t[i+2]); } pt p = {0,0}; if(res.first==res.second || res.first==p || res.second==p|| det(res.first,res.second)==0) { cout<<-1<<endl; return 0; }else { cout<<abs(res.first.first*res.second.second-res.first.second*res.second.first)<<endl; 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...