제출 #1002979

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002979		Lalic	Izvanzemaljci (COI21_izvanzemaljci)	C++17	5 / 100	16 ms	3164 KiB

izvanzemaljci

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int MAXN = 1e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);

pair<int, pair<pii, pii>> getBest(int n, vector<pii> arr){
	int mxy=-INF, mny=INF;
	vector<int> esq(n-1);
	vector<pii> coord(n-1);
	for(int i=0;i<n-1;i++){
		mxy=max(mxy, arr[i].se); mny=min(mny, arr[i].se);
		esq[i]=max({arr[i].fi-arr[0].fi, mxy-mny, 1});
		coord[i]={arr[i].fi-esq[i], mny};
	}
	
	int best=INF;
	pii cor1={-1, -1}, cor2={-1, -1};
	
	mxy=-INF, mny=INF;
	for(int i=n-1;i>=1;i--){
		mxy=max(mxy, arr[i].se); mny=min(mny, arr[i].se);
		if(arr[i-1].fi!=arr[i].fi){
			int curr=max({arr[n-1].fi-arr[i].fi, mxy-mny, 1});
			if(max(curr, esq[i-1])<best){
				best=max(curr, esq[i-1]);
				cor1=coord[i-1];
				cor2={arr[i].fi, mny};
			}
		}
	}
	
	return {best, {cor1, cor2}};
}

void solve(){
	int n, k; cin >> n >> k;
	
	vector<pii> arr(n);
	for(auto& [a, b] : arr) cin >> a >> b;
	
	if(k==1){
		int mnx=INF, mxx=-INF, mny=INF, mxy=-INF;
		for(auto [a, b]: arr) mnx=min(mnx, a), mxx=max(mxx, a), mny=min(mny, b), mxy=max(mxy, b);
		cout << mnx << " " << mny << " " << max({mxx-mnx, mxy-mny, 1}) << "\n";
	}
	else if(k==2){
		sort(all(arr));
		pair<int, pair<pii, pii>> res = getBest(n, arr);
		for(int i=0;i<n;i++){
			int aux=arr[i].se;
			arr[i].se=arr[i].fi;
			arr[i].fi=aux;
		}
		sort(all(arr));
		pair<int, pair<pii, pii>> res1 = getBest(n, arr);
		swap(res1.se.fi.fi, res1.se.fi.se); swap(res1.se.se.fi, res1.se.se.se);
		if(res1.fi<res.fi) swap(res, res1);
		
		cout << res.se.fi.fi << " " << res.se.fi.se << " " << res.fi << "\n";
		cout << res.se.se.fi << " " << res.se.se.se << " " << res.fi << "\n";
	}
}
	

int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	int tt=1;
	//~ cin >> tt;
	while(tt--) solve();
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 21
• Subtask 3: 0 / 12
• Subtask 4: 0 / 30
• Subtask 5: 0 / 32