Submission #1329209

#TimeUsernameProblemLanguageResultExecution timeMemory
1329209vlomaczkIOI 바이러스 (JOI21_fever)C++20
0 / 100
0 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>;

int best = 1;

struct Point {
	ll x, y;
};

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

void rotate(int n, vector<Point> &pkt) {
	for(int 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);

	int n;
	cin >> n;
	vector<Point> pkt(n);
	for(int i=0; i<n; ++i) cin >> pkt[i].x >> pkt[i].y;
	for(int i=n; i>=0; --i) {
		pkt[i].x -= pkt[0].x;
		pkt[i].y -= pkt[0].y;
		pkt[i].x *= 2;
		pkt[i].y *= 2;
	}
	for(int i=0; i<4; ++i) {
		best = max(best, solve(n, pkt));
		rotate(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...