oj.uz

Submission #167093

# Submission time Handle Problem Language Result Execution time Memory
167093 2019-12-05T14:36:31 Z cgiosy None (KOI18_footprint) C++17
14 / 100
 4 ms 508 KB 
#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) break;
		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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 4 ms 508 KB Output is correct
8 Correct 4 ms 504 KB Output is correct
9 Correct 4 ms 504 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 4 ms 504 KB Output is correct
12 Correct 4 ms 504 KB Output is correct
13 Correct 4 ms 504 KB Output is correct
14 Correct 4 ms 508 KB Output is correct
15 Correct 4 ms 504 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 4 ms 508 KB Output is correct
8 Correct 4 ms 504 KB Output is correct
9 Correct 4 ms 504 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 4 ms 504 KB Output is correct
12 Correct 4 ms 504 KB Output is correct
13 Correct 4 ms 504 KB Output is correct
14 Correct 4 ms 508 KB Output is correct
15 Correct 4 ms 504 KB Output is correct
16 Incorrect 2 ms 376 KB Output isn't correct
17 Halted 0 ms 0 KB -