Submission #1358072

#TimeUsernameProblemLanguageResultExecution timeMemory
1358072thorfinn공룡 발자국 (KOI18_footprint)C++20
100 / 100
1382 ms327672 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;

struct Angle {
	int x, y;
	int t;
	Angle(int x, int y, int t=0) : x(x), y(y), t(t) {}
	Angle operator-(Angle b) const { return {x-b.x, y-b.y, t}; }
	int half() const {
		assert(x || y);
		return y < 0 || (y == 0 && x < 0);
	}
	Angle t90() const { return {-y, x, t + (half() && x >= 0)}; }
	Angle t180() const { return {-x, -y, t + half()}; }
	Angle t360() const { return {x, y, t + 1}; }
};

bool operator<=(Angle a, Angle b) {
	// add a.dist2() and b.dist2() to also compare distances
	return make_tuple(a.t, a.half(), a.y * (ll)b.x) <=
	       make_tuple(b.t, b.half(), a.x * (ll)b.y);
}


bool operator<(Angle a, Angle b) {
	// add a.dist2() and b.dist2() to also compare distances
	return make_tuple(a.t, a.half(), a.y * (ll)b.x) <
	       make_tuple(b.t, b.half(), a.x * (ll)b.y);
}

// Given two points, this calculates the smallest angle between
// them, i.e., the angle that covers the defined line segment.
pair<Angle, Angle> segmentAngles(Angle a, Angle b) {
	if (b < a) swap(a, b);
	return (b < a.t180() ?
	        make_pair(a, b) : make_pair(b, a.t360()));
}
Angle operator+(Angle a, Angle b) { // point a + vector b
	Angle r(a.x + b.x, a.y + b.y, a.t);
	if (a.t180() < r) r.t--;
	return r.t180() < a ? r.t360() : r;
}
Angle angleDiff(Angle a, Angle b) { // angle b - angle a
	int tu = b.t - a.t; a.t = b.t;
	return {a.x*b.x + a.y*b.y, a.x*b.y - a.y*b.x, tu - (b < a)};
}


int dp[mxN][mxN][2];
pii trace[mxN][mxN][2];
vector<pair<Angle, int>> lef[mxN], rig[mxN];

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++) {
		for (int j = 1; j <= n; j++) {
			if (j < i) lef[i].pb(make_pair(Angle(a[j].fi - a[i].fi, a[j].se - a[i].se, 0), j));
			if (j > i) rig[i].pb(make_pair(Angle(a[j].fi - a[i].fi, a[j].se - a[i].se, 0), j));
		}

		sort(all(lef[i]));
		sort(all(rig[i]));
	}


	memset(dp, -0x3f, sizeof(dp));
	int res = dp[0][0][0];
	array<int, 3> path = {1, 1, 1};

	for (int i = 2; i <= n; i++) dp[i][1][0] = 2;


	for (int i = 2; i <= n; i++) {
		for (int cur = 0; cur < 2; cur++) {
			int l = 0, r = 0;
			deque<pii> dq;
			for (auto it : rig[i]) {
				if (cross3(a[1], a[i], a[it.se]) == 0) continue;
				while (l < sz(lef[i]) + sz(lef[i]) && (l < sz(lef[i]) ? lef[i][l].fi : lef[i][l - sz(lef[i])].fi.t360()) <= (cur == 1 ? it.fi.t180() : it.fi)) {
					++l;
					while (sz(dq) && dq.front().se < l) dq.pop_front();
				}
				r = max(l, r);
				while (r < sz(lef[i]) + sz(lef[i]) && (r < sz(lef[i]) ? lef[i][r].fi : lef[i][r - sz(lef[i])].fi.t360()) < (cur == 1 ? it.fi.t360() : it.fi.t180())) {
					int val;
					if (r < sz(lef[i])) val = dp[i][lef[i][r].se][cur];
					else val = dp[i][lef[i][r - sz(lef[i])].se][cur];
					if (val > 0) {
						while (sz(dq) && dq.back().fi < dp[i][lef[i][r % sz(lef[i])].se][cur]) dq.pop_back();
						dq.push_back(make_pair(dp[i][lef[i][r % sz(lef[i])].se][cur], r));
					}
					++r;
				}
				assert(l <= r);
				if (sz(dq)) {
					int idx;
					if (dq.front().se < sz(lef[i])) idx = lef[i][dq.front().se].se;
					else idx = lef[i][dq.front().se - sz(lef[i])].se;
					if (maxi(dp[it.se][i][cur ^ 1], dp[i][idx][cur] + 1)) {
						trace[it.se][i][cur ^ 1] = {i, idx};
					}
				}
			}
		}
	}	

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			if (maxi(res, dp[i][j][0])) {
				path = {i, j, 0};
			}
		}
	}

	// cout << dp[2][1][0] << ' ' << dp[3][2][1] << ' ' << dp[4][3][0] << ' ' << dp[5][4][1] << '\n';


	if (res >= 4) {
		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));
		cout << sz(ans) << '\n';
		for (auto it : ans) cout << a[it].fi << ' ' << a[it].se << '\n';
	} else {
		cout << 0 << '\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...