This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator <<(auto& o, pair<auto, auto> p) {return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator <<(auto& o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cout<<"["#X"]"<<X<<endl;
#else
#define debug(X) {}
#endif
#define int long long
int sqr(int a) {return a*a;}
struct vec
{
int x, y;
int nx = 0, ny = 0;
int cnt = 0;
vec(){x=0;y=0;}
vec(int _x, int _y)
{
x = _x; y = _y;
if(!(x != 0 || y != 0)) nx = 0, ny = 0;
else nx = x/__gcd(x, y), ny = y/__gcd(x, y);
if(nx != 0)
cnt = x / nx;
if(ny != 0)
cnt = y / ny;
}
friend bool operator < (const vec& obj1, const vec& obj2)
{
if(sqr(obj1.x)+sqr(obj1.y) < sqr(obj2.x)+sqr(obj2.y)) return true;
if(sqr(obj1.x)+sqr(obj1.y) > sqr(obj2.x)+sqr(obj2.y)) return false;
return make_pair(obj1.x, obj1.y) < make_pair(obj2.x, obj2.y);
}
};
int operator *(vec& obj1, vec& obj2)
{
return obj1.x*obj2.y - obj1.y*obj2.x;
}
auto&operator <<(auto& o, vec V) {return o<<"["<<V.x<<";"<<V.y<<"]";}
vec _gcd(vec a, vec b, pair<int, int> norm)
{
return vec(__gcd(a.cnt, b.cnt)*norm.first,
__gcd(a.cnt, b.cnt)*norm.second);
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
int prevX, prevY;
map<pair<int, int>, vec> norms;
set<vec> alive;
auto add = [&](vec a)
{
auto v = norms[make_pair(a.nx, a.ny)];
if(alive.find(v) != alive.end()) alive.erase(v);
norms[make_pair(a.nx, a.ny)] = _gcd(a, v, {a.nx, a.ny});
if(norms[make_pair(a.nx, a.ny)].x != 0 || norms[make_pair(a.nx, a.ny)].y != 0)
alive.insert(norms[make_pair(a.nx, a.ny)]);
};
for(int i=0;i<n;i++)
{
int x, y;
cin>>x>>y;
if(i != 0)
add(vec(-prevX+x, -prevY+y));
prevX = x;
prevY = y;
}
srand(1234);
while(alive.size() > 2)
{
debug(alive);
auto it = alive.begin();
vector<vec> vc;
vc.push_back(*it); it++;
vc.push_back(*it);
it = alive.end();
it--;
vc.push_back(*it);
random_shuffle(vc.begin(), vc.end());
vec a = vc[0];
vec b = vc[1];
vec c = vc[2];
int k = c*b/(a*b);
int l = a*c/(a*b);
alive.erase(c);
debug(alive);
c.x -= k*a.x;
c.y -= k*a.y;
c.x -= l*b.x;
c.y -= l*b.y;
vec p = vec(c.x, c.y);
add(p);
}
if(alive.size() <= 1) {cout<<-1; return 0;}
auto it = alive.begin();
auto a = *it; it++;
auto b = *it;
cout<<abs(a*b);
}
Compilation message (stderr)
Main.cpp:72:2: error: extended character is not valid in an identifier
72 | srand(1234);
| ^
Main.cpp:73:2: error: extended character is not valid in an identifier
73 | while(alive.size() > 2)
| ^
Main.cpp:73:5: error: extended character is not valid in an identifier
73 | while(alive.size() > 2)
| ^
Main.cpp:77:2: error: extended character is not valid in an identifier
77 | vector<vec> vc;
| ^
Main.cpp:77:5: error: extended character is not valid in an identifier
77 | vector<vec> vc;
| ^
Main.cpp:77:8: error: extended character is not valid in an identifier
77 | vector<vec> vc;
| ^
Main.cpp:77:11: error: extended character is not valid in an identifier
77 | vector<vec> vc;
| ^
Main.cpp:78:2: error: extended character is not valid in an identifier
78 | vc.push_back(*it); it++;
| ^
Main.cpp:78:5: error: extended character is not valid in an identifier
78 | vc.push_back(*it); it++;
| ^
Main.cpp:78:8: error: extended character is not valid in an identifier
78 | vc.push_back(*it); it++;
| ^
Main.cpp:78:11: error: extended character is not valid in an identifier
78 | vc.push_back(*it); it++;
| ^
Main.cpp:79:2: error: extended character is not valid in an identifier
79 | vc.push_back(*it);
| ^
Main.cpp:79:5: error: extended character is not valid in an identifier
79 | vc.push_back(*it);
| ^
Main.cpp:79:8: error: extended character is not valid in an identifier
79 | vc.push_back(*it);
| ^
Main.cpp:79:11: error: extended character is not valid in an identifier
79 | vc.push_back(*it);
| ^
Main.cpp:80:2: error: extended character is not valid in an identifier
80 | it = alive.end();
| ^
Main.cpp:80:5: error: extended character is not valid in an identifier
80 | it = alive.end();
| ^
Main.cpp:80:8: error: extended character is not valid in an identifier
80 | it = alive.end();
| ^
Main.cpp:80:11: error: extended character is not valid in an identifier
80 | it = alive.end();
| ^
Main.cpp:81:2: error: extended character is not valid in an identifier
81 | it--;
| ^
Main.cpp:81:5: error: extended character is not valid in an identifier
81 | it--;
| ^
Main.cpp:81:8: error: extended character is not valid in an identifier
81 | it--;
| ^
Main.cpp:81:11: error: extended character is not valid in an identifier
81 | it--;
| ^
Main.cpp:82:2: error: extended character is not valid in an identifier
82 | vc.push_back(*it);
| ^
Main.cpp:82:5: error: extended character is not valid in an identifier
82 | vc.push_back(*it);
| ^
Main.cpp:82:8: error: extended character is not valid in an identifier
82 | vc.push_back(*it);
| ^
Main.cpp:82:11: error: extended character is not valid in an identifier
82 | vc.push_back(*it);
| ^
Main.cpp:83:2: error: extended character is not valid in an identifier
83 | random_shuffle(vc.begin(), vc.end());
| ^
Main.cpp:83:5: error: extended character is not valid in an identifier
83 | random_shuffle(vc.begin(), vc.end());
| ^
Main.cpp:83:8: error: extended character is not valid in an identifier
83 | random_shuffle(vc.begin(), vc.end());
| ^
Main.cpp:83:11: error: extended character is not valid in an identifier
83 | random_shuffle(vc.begin(), vc.end());
| ^
Main.cpp:84:2: error: extended character is not valid in an identifier
84 | vec a = vc[0];
| ^
Main.cpp:84:5: error: extended character is not valid in an identifier
84 | vec a = vc[0];
| ^
Main.cpp:84:8: error: extended character is not valid in an identifier
84 | vec a = vc[0];
| ^
Main.cpp:84:11: error: extended character is not valid in an identifier
84 | vec a = vc[0];
| ^
Main.cpp:85:2: error: extended character is not valid in an identifier
85 | vec b = vc[1];
| ^
Main.cpp:85:5: error: extended character is not valid in an identifier
85 | vec b = vc[1];
| ^
Main.cpp:85:8: error: extended character is not valid in an identifier
85 | vec b = vc[1];
| ^
Main.cpp:85:11: error: extended character is not valid in an identifier
85 | vec b = vc[1];
| ^
Main.cpp:86:2: error: extended character is not valid in an identifier
86 | vec c = vc[2];
| ^
Main.cpp:86:5: error: extended character is not valid in an identifier
86 | vec c = vc[2];
| ^
Main.cpp:86:8: error: extended character is not valid in an identifier
86 | vec c = vc[2];
| ^
Main.cpp:86:11: error: extended character is not valid in an identifier
86 | vec c = vc[2];
| ^
Main.cpp:87:2: error: extended character is not valid in an identifier
87 | int k = c*b/(a*b);
| ^
Main.cpp:87:5: error: extended character is not valid in an identifier
87 | int k = c*b/(a*b);
| ^
Main.cpp:87:8: error: extended character is not valid in an identifier
87 | int k = c*b/(a*b);
| ^
Main.cpp:39:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
39 | auto&operator <<(auto& o, vec V) {return o<<"["<<V.x<<";"<<V.y<<"]";}
| ^~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:72:2: error: '\U000000a0srand' was not declared in this scope; did you mean 'srand'?
72 | srand(1234);
| ^~~~~~
| srand
Main.cpp:73:2: error: '\U000000a0' was not declared in this scope
73 | while(alive.size() > 2)
| ^