| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1084088 | raczek | Portal (BOI24_portal) | C++17 | 0 ms | 0 KiB |
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);
}