제출 #1357983

#제출 시각아이디문제언어결과실행 시간메모리
1357983thorfinn공룡 발자국 (KOI18_footprint)C++20
0 / 100
2096 ms97032 KiB
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define emb emplace_back
#define pb push_back
#define mt make_tuple
#define fi first
#define se second
#define uniq(x) (x).erase(unique(all(x)), x.end())
#define BIT(x, i) (((x)>>(i))&1)
#define MASK(i) (1LL<<(i))
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vl;
template<typename T1, typename T2> bool mini(T1 &a, T2 b) 
	{if(a>b) a=b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b) 
	{if(a<b) a=b; else return 0; return 1;}

const int mxN = 3e3 + 7;
const int md = 1e9 + 7;
const int inf = 1e9 + 7;

int dp[mxN][mxN][2];
pii trace[mxN][mxN][2];


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

	int n;
	cin >> n;
	vector<pii> a(n + 7);
	for (int i = 1; i <= n; i++) {
		cin >> a[i].fi >> a[i].se;
		if (i > 1 && a[1].se > a[i].se) {
			swap(a[1], a[i]);
		}
	}	

	auto cross = [&](pii a, pii b) {
		return 1LL * a.fi  * b.se - 1LL * a.se * b.fi;
	};

	auto cross3 = [&](pii a, pii b, pii c) {
		pii t1 = make_pair(b.fi - a.fi, b.se - a.se);
		pii t2 = make_pair(c.fi - a.fi, c.se - a.se);
		return cross(t1, t2);
	};

	auto sq = [&](pii a, pii b) {
		return 1LL * (a.fi - b.fi) * (a.fi - b.fi) + 1LL * (a.se - b.se) * (a.se - b.se);
	};

	sort (a.begin() + 2, a.begin() + 1 + n, [&](pii x, pii y){
		ll temp = cross3(a[1], x, y);
		if (temp != 0) return temp > 0;
		return sq(a[1], x) < sq(a[1], y); 
	});

	// for (int i = 1; i <= n; i++) cout << a[i].fi << ' ' << a[i].se << '\n';

	memset(dp, -0x3f, sizeof(dp));
	int res = dp[0][0][0];
	array<int, 3> path;
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			for (int cur = 0; cur < 2; cur++) {
				if (j == 1) {
					if (cur == 0) dp[i][j][cur] = 2;
				} else {
					for (int k = 1; k < j; k++) {
						if (cur == 1) { 
							if (cross3(a[k], a[j], a[i]) > 0) {
								if (maxi(dp[i][j][cur], dp[j][k][cur ^ 1] + 1)) {
									trace[i][j][cur] = {j, k};
								}
							}
						} else {
							if (cross3(a[k], a[j], a[i]) < 0) {
								if (maxi(dp[i][j][cur], dp[j][k][cur ^ 1] + 1)) {
									trace[i][j][cur] = {j, k};
								}
							}
						}
					}
				}
				if (cur == 0 && maxi(res, dp[i][j][cur])) {
					path = {i, j, cur};
				}
			}
		}
	}

	vector<int> ans;
	ans.pb(path[0]);
	ans.pb(path[1]);
	while (path[0] != 0 && path[1] != 0) {
		pii temp = trace[path[0]][path[1]][path[2]];
		path[0] = temp.fi;
		path[1] = temp.se;
		path[2] ^= 1;
		if (path[1] > 0) ans.pb(path[1]);
	}


	reverse(all(ans));

	if (sz(ans) < 4) {
		cout << 0 << '\n';
		return 0;
	}

	cout << sz(ans) << '\n';
	for (auto it : ans) cout << a[it].fi << ' ' << a[it].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...