Submission #1329223

#TimeUsernameProblemLanguageResultExecution timeMemory
1329223vlomaczkIOI Fever (JOI21_fever)C++20
19 / 100
1 ms344 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll best = 1;

struct Poll {
	ll x, y;
};

ll solve(ll n, vector<Poll> &pkt) {
	// for(auto[x,y] : pkt) cout << x << " " << y << "\n";
	// cout << "\n";

	priority_queue<pair<ll, pair<ll, ll>>> pq; // 0-top, 1-bot, 2-right, 3-left
	vector<ll> vis(n);
	pq.push({0, {0, 0}});
	ll res = 0;
	vis[0] = 1;
	while(pq.size()) {
		auto[dv, stat] = pq.top(); pq.pop();
		dv*=-1; auto[v, k] = stat;
		// cout << v << " " << k << "\n";
		auto[x,y] = pkt[v]; res++;
		vector<ll> przek_roz, przek_sum, X, Y;
		for(ll i=0; i<n; ++i) {
			if(i==v) continue;
			if(pkt[i].x==x) X.push_back(i);
			if(pkt[i].y==y) Y.push_back(i);
			if(x-y == pkt[i].x-pkt[i].y) przek_roz.push_back(i);
			if(x+y == pkt[i].x+pkt[i].y) przek_sum.push_back(i);
		}
		if(k < 2) {
			for(auto i : X) {
				ll moment = pkt[i].y - y; moment/=2;
				if(k==1) moment *=-1;
				if(!vis[i] && moment >= dv) {
					vis[i] = 1;
					pq.push({-moment, {i, k^1}});
				}
			}
			for(auto i : przek_sum) {
				ll moment = pkt[i].y - y;
				if(k==1) {
					moment*=-1;
				}
				if(!vis[i] && moment >= dv) {
					vis[i] = 1;
					pq.push({-moment, {i, 2^(k==1)}});
				}
			}
			for(auto i : przek_roz) {
				ll moment = pkt[i].y - y;
				if(k==1) {
					moment*=-1;
				}
				if(!vis[i] && moment >= dv) {
					vis[i] = 1;
					pq.push({-moment, {i, 2^(k==0)}});
				}
			}
		} else {
			for(auto i : Y) {
				ll moment = pkt[i].x - x; moment/=2;
				if(k==3) moment *=-1;
				if(!vis[i] && moment >= dv) {
					vis[i] = 1;
					pq.push({-moment, {i, k^1}});
				}
			}
			for(auto i : przek_sum) {
				ll moment = pkt[i].x - x;
				if(k==3) {
					moment*=-1;
				}
				if(!vis[i] && moment >= dv) {
					vis[i] = 1;
					pq.push({-moment, {i, (k==3)}});
				}
			}
			for(auto i : przek_roz) {
				ll moment = pkt[i].x - x;
				if(k==3) {
					moment*=-1;
				}
				if(!vis[i] && moment >= dv) {
					vis[i] = 1;
					pq.push({-moment, {i, (k==2)}});
				}
			}
		}
	}
	return res;
}

void rotate(ll n, vector<Poll> &pkt) {
	for(ll i=0; i<n; ++i) {
		auto[x, y] = pkt[i];
		pkt[i] = {-y, x};
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll n;
	cin >> n;
	vector<Poll> pkt(n);
	for(ll i=0; i<n; ++i) cin >> pkt[i].x >> pkt[i].y;
	for(ll i=n-1; i>=0; --i) {
		pkt[i].x -= pkt[0].x;
		pkt[i].y -= pkt[0].y;
		pkt[i].x *= 2;
		pkt[i].y *= 2;
	}
	for(ll i=0; i<4; ++i) {
		best = max(best, solve(n, pkt));
		rotate(n, pkt);
	}
	// rotate(n, pkt);
	// best = solve(n, pkt);
	cout << best << "\n";

	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...
#Verdict Execution timeMemoryGrader output
Fetching results...