Submission #284842

#	Time	Username	Problem	Language	Result	Execution time	Memory
284842		youngyojun	공룡 발자국 (KOI18_footprint)	C++17	100 / 100	1355 ms	110968 KiB

footprint

#include <bits/stdc++.h>
#define eb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll operator * (const pll &a, const pll &b) { return a.fi * b.se - b.fi * a.se; }
ll ccw(const pll &a, const pll &b, const pll &c) { return a*b + b*c + c*a; }

int D[3005][3005], RD[3005][3005];
int E[3005][3005], RE[3005][3005];

int NV[3005], NVn;
int PV[3005], PVn;

pll P[3005];

int N;

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

	cin >> N;
	for(int i = 0; i < N; i++) {
		cin >> P[i].fi >> P[i].se;
		if(P[i].se < P[0].se) swap(P[0], P[i]);
	}
	N--;
	sort(P+1, P+N+1, [&](const pll &a, const pll &b) { return ccw(P[0], a, b) > 0; });

	for(int i = 1; i <= N; i++) {
		D[i][0] = 2;

		NVn = PVn = 0;
	{
		int k = i+1;
		for(; k <= N && !ccw(P[0], P[i], P[k]); k++);
		for(; k <= N; k++) NV[NVn++] = k;
	}
	{
		PV[PVn++] = 0;
		int j = i-1;
		for(; j && !ccw(P[0], P[i], P[j]); j--);
		for(; j; j--) PV[PVn++] = j;
	}
		sort(NV, NV+NVn, [&](int a, int b) { return ccw(P[i], P[a], P[b]) > 0; });
		sort(PV, PV+PVn, [&](int a, int b) { return ccw(P[i], P[a], P[b]) > 0; });

		for(int ki = 0, k, ji = 0, j, mx = 0, mxj; ki < NVn; ki++) {
			k = NV[ki];
			for(; ji < PVn; ji++) {
				j = PV[ji];
				if(ccw(P[j], P[i], P[k]) <= 0) break;
				if(mx < D[i][j]) {
					mx = D[i][j];
					mxj = j;
				}
			}
			if(mx) {
				E[k][i] = mx + 1;
				RE[k][i] = mxj;
			}
		}

		for(int ki = NVn-1, k, ji = PVn-1, j, mx = 0, mxj; 0 <= ki; ki--) {
			k = NV[ki];
			for(; 0 <= ji; ji--) {
				j = PV[ji];
				if(ccw(P[j], P[i], P[k]) >= 0) break;
				if(mx < E[i][j]) {
					mx = E[i][j];
					mxj = j;
				}
			}
			if(mx) {
				D[k][i] = mx + 1;
				RD[k][i] = mxj;
			}
		}
	}

{
	int Ans = 0, I, J;
	for(int i = N; i; i--) for(int j = i-1; j; j--)
		if(Ans < D[i][j]) {
			Ans = D[i][j];
			I = i; J = j;
		}
	
	if(Ans < 4) { puts("0"); exit(0); }
	cout << Ans << '\n';

	vector<int> V;
	for(int t = 0; 2 < Ans; Ans--, t ^= 1) {
		V.eb(I);
		I = (t ? RE : RD)[I][J];
		swap(I, J);
	}
	V.eb(I); V.eb(J);

	reverse(V.begin(), V.end());
	for(int v : V) cout << P[v].fi << ' ' << P[v].se << '\n';
}
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 12 / 12
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45