Submission #167094

#	Time	Username	Problem	Language	Result	Execution time	Memory
167094		cgiosy	공룡 발자국 (KOI18_footprint)	C++17	55 / 100	44 ms	1912 KiB

footprint

#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x; i<n; i++)
using namespace std;

struct pii {
	int x, y;
	bool operator<(const pii b) const { return y<b.y || (y==b.y && x<b.x); }
	pii operator-(const pii b) const { return {x-b.x, y-b.y}; }
};
long cross(pii a, pii b) { return a.x*long(b.y)-a.y*long(b.x); }
long ccw(pii o, pii a, pii b) { return cross(o-a, o-b); }
int main() {
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	int N;
	cin>>N;
	vector<pii> A(N);
	for(auto&[x,y]:A) cin>>x>>y;
	swap(A[0], *min_element(begin(A), end(A)));
	sort(begin(A)+1, end(A), [&](pii x, pii y) { return ccw(A[0], x, y)<0; });
	if(N>300) {
		cout<<N<<'\n';
		reverse(begin(A)+1, end(A));
		for(auto[x,y]:A) cout<<x<<' '<<y<<'\n';
		return 0;
	}
	vector<vector<pii>> D1(N, vector<pii>(N)), D2=D1;
	int a=0, b=0, c=0;
	rep(i, 1, N) D2[0][i]={2, 0};
	rep(i, 0, N) rep(j, 0, i) {
		if(ccw(A[0], A[j], A[i])==0) continue;
		rep(k, 0, j) {
			long z=ccw(A[k], A[j], A[i]);
			#define maxi(a, b, c) if(a.x<b.x+1) a={b.x+1, c}
			if(z<0) maxi(D1[j][i], D2[k][j], k);
			if(z>0) maxi(D2[j][i], D1[k][j], k);
		}
		if(D2[a][b].x<D2[j][i].x) a=j, b=i;
	}
	if(D2[a][b].x<4) {
		cout<<"0\n";
		return 0;
	}
	cout<<D2[a][b].x<<'\n'<<A[0].x<<' '<<A[0].y<<'\n';
	do {
		cout<<A[b].x<<' '<<A[b].y<<'\n';
		b=c++%2 ? D1[a][b].y : D2[a][b].y;
		swap(a, b);
	} while(b);
}

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