Submission #1084089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084089		raczek	Portal (BOI24_portal)	C++17	100 / 100	317 ms	20648 KiB

Main

#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: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<<"]";}
      |                  ^~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 29 / 29
• Subtask 5: 15 / 15
• Subtask 6: 35 / 35