Submission #284848

#TimeUsernameProblemLanguageResultExecution timeMemory
284848youngyojun공룡 발자국 (KOI18_footprint)C++17
41 / 100
2104 ms162708 KiB
#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; }

ll MP[3005][3005];
inline ll ccw(int a, int b, int c) { return MP[a][b] + MP[b][c] - MP[a][c]; }

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++) for(int j = 0; j < i; j++) {
		MP[i][j] = P[i] * P[j];
		MP[j][i] = -MP[i][j];
	}

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

		NVn = PVn = 0;
	{
		int k = i+1;
		for(; k <= N && !ccw(0, i, k); k++);
		for(; k <= N; k++) NV[NVn++] = k;
	}
	{
		PV[PVn++] = 0;
		int j = i-1;
		for(; j && !ccw(0, i, j); j--);
		for(; j; j--) PV[PVn++] = j;
	}
		sort(NV, NV+NVn, [&](int a, int b) { return ccw(i, a, b) > 0; });
		sort(PV, PV+PVn, [&](int a, int b) { return ccw(i, a, 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(j, i, 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(j, i, 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...