Submission #167589

#	Time	Username	Problem	Language	Result	Execution time	Memory
167589		cgiosy	공룡 발자국 (KOI18_footprint)	C++17	100 / 100	59 ms	632 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; });
	vector<pii> D1(N), D2(N);
	int a=0, c=0;
	rep(i, 1, N) D2[i]={2, 0};
	rep(i, 0, N) {
		rep(j, 0, i) {
			if(ccw(A[0], A[j], A[i])==0) continue;
			#define maxi(a, b, c, d) \
				if(ccw(A[b.y], A[j], A[i])*d<0 \
				&& (a.x<b.x+1 || (a.x==b.x+1 && ccw(A[i], A[a.y], A[j])*d<0))) \
					a={b.x+1, c}
			maxi(D1[i], D2[j], j, 1);
			maxi(D2[i], D1[j], j, -1);
		}
		if(D2[a].x<D2[i].x) a=i;
	}
	if(D2[a].x<4) {
		cout<<"0\n";
		return 0;
	}
	cout<<D2[a].x<<'\n'<<A[0].x<<' '<<A[0].y<<'\n';
	do cout<<A[a].x<<' '<<A[a].y<<'\n'; while(a=c++%2 ? D1[a].y : D2[a].y);
}

Compilation message (stderr)

footprint.cpp: In function 'int main()':
footprint.cpp:40:45: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  do cout<<A[a].x<<' '<<A[a].y<<'\n'; while(a=c++%2 ? D1[a].y : D2[a].y);
                                            ~^~~~~~~~~~~~~~~~~~~~~~~~~~

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