Submission #64203

#	Time	Username	Problem	Language	Result	Execution time	Memory
64203		gs14004	공룡 발자국 (KOI18_footprint)	C++17	100 / 100	1787 ms	84672 KiB

footprint

#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 3005;

int n;
pi a[MAXN];
pi dp[MAXN][MAXN][2];
int idx[MAXN];

struct st{
	pi pnt;
	int idx;
};

lint ccw(pi a, pi b, pi c){
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}

void trace(int x, int y, int z){
	printf("%d %d\n", a[y].first, a[y].second);
	if(dp[x][y][z].first == 0) return;
	trace(y, dp[x][y][z].second, 1-z);
}

int main(){
	cin >> n;
	for(int i=0; i<n; i++) cin >> a[i].first >> a[i].second;
	sort(a, a+n, [&](const pi &a, const pi &b){
		return a.second < b.second;
	});
	sort(a+1, a+n, [&](const pi &p, const pi &q){
		return ccw(a[0], p, q) > 0;
	});
	int grp = 1;
	for(int i=1; i<n; i++){
		if(ccw(a[0], a[i-1], a[i]) != 0) grp++;
		idx[i] = grp;
	}
	for(int i=n-1; i>=1; i--){
		vector<int> up, dn;
		for(int j=1; j<n; j++){
			if(idx[j] < idx[i]) dn.push_back(j);
			if(idx[j] > idx[i]) up.push_back(j);
		}
		sort(up.begin(), up.end(), [&](const int &p, const int &q){
			return ccw(a[i], a[p], a[q]) > 0;
		});
		sort(dn.begin(), dn.end(), [&](const int &p, const int &q){
			return ccw(a[i], a[p], a[q]) > 0;
		});
		int ptr = 0;
		pi curmax = pi(-1e9, -1);
		for(auto &j : dn){
			while(ptr < up.size() && ccw(a[j], a[i], a[up[ptr]]) < 0){
				auto l = dp[i][up[ptr]][0].first + 1;
				curmax = max(curmax, pi(l, up[ptr]));
				ptr++;
			}
			dp[j][i][1]= curmax;
		}
		reverse(dn.begin(), dn.end());
		reverse(up.begin(), up.end());
		ptr = 0;
		curmax = pi(0, -1);
		for(auto &j : dn){
			while(ptr < up.size() && ccw(a[j], a[i], a[up[ptr]]) > 0){
				auto l = dp[i][up[ptr]][1].first + 1;
				curmax = max(curmax, pi(l, up[ptr]));
				ptr++;
			}
			dp[j][i][0]= curmax;
		}
	}
	tuple<int, int, int> ans = make_tuple(-100, -1, -1);
	for(int i=n-1; i>=1; i--){
		for(int j=i+1; j<n; j++){
			if(idx[i] == idx[j]) continue;
			ans = max(ans, make_tuple(dp[i][j][1].first, i, j));
		}
	}
	int x, y, z; tie(x, y, z) = ans;
	if(x < 0){
		puts("0");
		return 0;
	}	
	cout << x + 3 << endl;
	printf("%d %d\n", a[0].first, a[0].second);
	printf("%d %d\n", a[y].first, a[y].second);
	trace(y, z, 1);
}

Compilation message (stderr)

footprint.cpp: In function 'int main()':
footprint.cpp:60:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(ptr < up.size() && ccw(a[j], a[i], a[up[ptr]]) < 0){
          ~~~~^~~~~~~~~~~
footprint.cpp:72:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(ptr < up.size() && ccw(a[j], a[i], a[up[ptr]]) > 0){
          ~~~~^~~~~~~~~~~

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