oj.uz

Submission #64579

# Submission time Handle Problem Language Result Execution time Memory
64579 2018-08-05T00:12:03 Z kjp4155 None (KOI18_footprint) C++17
100 / 100
 1963 ms 189160 KB 
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;

// 계산을 편리하게 하기 위한 Point구조체 및 몇가지 연산자 정의
struct Point{
	ll x,y,n;
};
Point operator - (Point a, Point b){
	return {a.x-b.x, a.y-b.y, a.n};
}
ll ccw(Point a, Point b){
	return a.x * b.y - a.y * b.x;
}

int N;
ll xbase = 0, ybase = 1e9;
ll X[5050], Y[5050];
vector<Point> v;

int dp1[5050][5050], dp2[5050][5050];
int prev1[5050][5050], prev2[5050][5050];

int main(){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		scanf("%lld%lld",&X[i],&Y[i]);
		if( ybase > Y[i] ){
			ybase = Y[i]; xbase = X[i];
		}
	}

	// 발뒤꿈치를 원점으로 하도록 점들을 평행이동시키자
	for(int i=1;i<=N;i++){
		X[i] -= xbase; Y[i] -= ybase;
		if( X[i] == 0 && Y[i] == 0 ) continue;
		v.push_back({X[i], Y[i], i});
	}

	// 나머지 점들(1,2,...,N-1)을 모두 반시계방향으로 정렬
	sort( v.begin(), v.end() , [](Point& a, Point& b){
		return ccw(a,b) > 0;
	} );

	v.push_back({0,0,0});

	// i를 고정시키고 슬라이딩 윈도우 기법으로 dp1[i][j], dp2[i][j]를 모두 채우자
	for(int i=0;i<v.size();i++){

		// 점들의 집합 L, R을 만들기
		// 세 점이 한 직선위에 있는 경우에 주의하자 
		vector<Point> L,R;
		for(int j=0;j<i;j++){
			if( ccw(v[j], v[i]) == 0 ) continue;
			R.push_back(v[j]);
		}
		for(int j=i+1;j<v.size();j++){
			if( j != v.size()-1 && ccw(v[j], v[i]) == 0 ) continue;
			L.push_back(v[j]);
		}

		// dp1을 채우기 위해 L,R을 반시계방향으로 정렬
		sort(L.begin(), L.end(), [i](Point a, Point b){
			return ccw(a-v[i], b-v[i]) > 0;
		});
		sort(R.begin(), R.end(), [i](Point a, Point b){
			return ccw(a-v[i], b-v[i]) > 0;
		});


		int pos = -1;
		int mx = 0, mxx = 0;
		
		// 슬라이딩 윈도우로 dp1 채우기
		for(auto p : L){

			while( pos+1 < R.size() && ccw( v[i]-p , R[pos+1]-p ) < 0 ){
				pos++;
				if( mx < dp2[ R[pos].n ][ v[i].n ] ){
					mx = dp2[ R[pos].n ][ v[i].n ];
					mxx = R[pos].n;
				}
			}

			if( dp1[ v[i].n ][ p.n ] < mx+1 ){
				dp1[ v[i].n ][ p.n ] = mx + 1;
				prev1[ v[i].n ][ p.n ] =mxx;
			}
			
		}

		// dp2를 채우기 위해 L,R을 시계방향으로 정렬
		sort(L.begin(), L.end(), [i](Point a, Point b){
			return ccw(a-v[i], b-v[i]) < 0;
		});
		sort(R.begin(), R.end(), [i](Point a, Point b){
			return ccw(a-v[i], b-v[i]) < 0;
		});

		// 슬라이딩 윈도우로 dp2 채우기
		pos = -1; mx = 0, mxx = 0;
		for(auto p : L){
			if( p.n == 0 ) continue;
			while( pos+1 < R.size() && ccw( v[i]-p , R[pos+1]-p ) > 0 ){
				pos++;
				if( mx < dp1[ R[pos].n ][ v[i].n ] ){
					mx = dp1[ R[pos].n ][ v[i].n ];
					mxx = R[pos].n;
				}
			}

			// 골은 적어도 두번째 점부터 시작하는 것에 유의
			if( mx >= 1 && dp2[ v[i].n ][ p.n ] < mx+1 ){
				dp2[ v[i].n ][ p.n ] = mx + 1;
				prev2[ v[i].n ][ p.n ] = mxx;
			}
			
		}
	}

	int mx = -1, mxx = 0;
	for(int i=1;i<=N;i++){
		if( mx < dp1[i][0] ){
			mx = dp1[i][0];
			mxx = i;
		}
	}

	// 발자국을 만들수 없는 경우 (발가락이 1개 이하)
	if( mx < 3 ){
		printf("0\n");
		return 0;
	}

	// 답이 되는 점들을 복원해 ansv에 넣기
	vector<pair<ll,ll>> ansv;
	int cur = mxx, nxt = 0;
	while( true ){
		ansv.push_back({X[cur]+xbase, Y[cur]+ybase});
		if( dp1[cur][nxt] == 1 ) break;
		int pre = prev1[cur][nxt];
		nxt = cur;
		cur = pre;

		ansv.push_back({X[cur]+xbase, Y[cur]+ybase});
		pre = prev2[cur][nxt];
		nxt = cur;
		cur = pre;
	}
	ansv.push_back({xbase, ybase});

	// 답 출력
	printf("%d\n", mx+1);
	reverse( ansv.begin(), ansv.end() );
	for(auto e : ansv) printf("%lld %lld\n",e.first, e.second);
}

Compilation message

footprint.cpp: In function 'int main()':
footprint.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++){
              ~^~~~~~~~~
footprint.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=i+1;j<v.size();j++){
                 ~^~~~~~~~~
footprint.cpp:62:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if( j != v.size()-1 && ccw(v[j], v[i]) == 0 ) continue;
        ~~^~~~~~~~~~~~~
footprint.cpp:81:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while( pos+1 < R.size() && ccw( v[i]-p , R[pos+1]-p ) < 0 ){
           ~~~~~~^~~~~~~~~~
footprint.cpp:108:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while( pos+1 < R.size() && ccw( v[i]-p , R[pos+1]-p ) > 0 ){
           ~~~~~~^~~~~~~~~~
footprint.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
footprint.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&X[i],&Y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1491 ms 160528 KB Output is correct
2 Correct 1511 ms 165636 KB Output is correct
3 Correct 1627 ms 165636 KB Output is correct
4 Correct 1669 ms 165756 KB Output is correct
5 Correct 1476 ms 165756 KB Output is correct
6 Correct 1624 ms 165788 KB Output is correct
7 Correct 1670 ms 165788 KB Output is correct
8 Correct 1652 ms 166300 KB Output is correct
9 Correct 1745 ms 166784 KB Output is correct
10 Correct 1472 ms 166784 KB Output is correct
11 Correct 1486 ms 166784 KB Output is correct
12 Correct 1645 ms 166784 KB Output is correct
13 Correct 1696 ms 170468 KB Output is correct
14 Correct 1707 ms 170468 KB Output is correct
15 Correct 1473 ms 170468 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 170468 KB Output is correct
2 Correct 2 ms 170468 KB Output is correct
3 Correct 2 ms 170468 KB Output is correct
4 Correct 3 ms 170468 KB Output is correct
5 Correct 2 ms 170468 KB Output is correct
6 Correct 3 ms 170468 KB Output is correct
7 Correct 3 ms 170468 KB Output is correct
8 Correct 2 ms 170468 KB Output is correct
9 Correct 2 ms 170468 KB Output is correct
10 Correct 2 ms 170468 KB Output is correct
11 Correct 3 ms 170468 KB Output is correct
12 Correct 2 ms 170468 KB Output is correct
13 Correct 3 ms 170468 KB Output is correct
14 Correct 3 ms 170468 KB Output is correct
15 Correct 3 ms 170468 KB Output is correct
16 Correct 2 ms 170468 KB Output is correct
17 Correct 2 ms 170468 KB Output is correct
18 Correct 3 ms 170468 KB Output is correct
19 Correct 3 ms 170468 KB Output is correct
20 Correct 3 ms 170468 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 170468 KB Output is correct
2 Correct 2 ms 170468 KB Output is correct
3 Correct 2 ms 170468 KB Output is correct
4 Correct 3 ms 170468 KB Output is correct
5 Correct 2 ms 170468 KB Output is correct
6 Correct 3 ms 170468 KB Output is correct
7 Correct 3 ms 170468 KB Output is correct
8 Correct 2 ms 170468 KB Output is correct
9 Correct 2 ms 170468 KB Output is correct
10 Correct 2 ms 170468 KB Output is correct
11 Correct 3 ms 170468 KB Output is correct
12 Correct 2 ms 170468 KB Output is correct
13 Correct 3 ms 170468 KB Output is correct
14 Correct 3 ms 170468 KB Output is correct
15 Correct 3 ms 170468 KB Output is correct
16 Correct 2 ms 170468 KB Output is correct
17 Correct 2 ms 170468 KB Output is correct
18 Correct 3 ms 170468 KB Output is correct
19 Correct 3 ms 170468 KB Output is correct
20 Correct 3 ms 170468 KB Output is correct
21 Correct 18 ms 170468 KB Output is correct
22 Correct 15 ms 170468 KB Output is correct
23 Correct 23 ms 170468 KB Output is correct
24 Correct 21 ms 170468 KB Output is correct
25 Correct 19 ms 170468 KB Output is correct
26 Correct 19 ms 170468 KB Output is correct
27 Correct 20 ms 170468 KB Output is correct
28 Correct 19 ms 170468 KB Output is correct
29 Correct 19 ms 170468 KB Output is correct
30 Correct 22 ms 170468 KB Output is correct
31 Correct 21 ms 170468 KB Output is correct
32 Correct 20 ms 170468 KB Output is correct
33 Correct 12 ms 170468 KB Output is correct
34 Correct 14 ms 170468 KB Output is correct
35 Correct 12 ms 170468 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1491 ms 160528 KB Output is correct
2 Correct 1511 ms 165636 KB Output is correct
3 Correct 1627 ms 165636 KB Output is correct
4 Correct 1669 ms 165756 KB Output is correct
5 Correct 1476 ms 165756 KB Output is correct
6 Correct 1624 ms 165788 KB Output is correct
7 Correct 1670 ms 165788 KB Output is correct
8 Correct 1652 ms 166300 KB Output is correct
9 Correct 1745 ms 166784 KB Output is correct
10 Correct 1472 ms 166784 KB Output is correct
11 Correct 1486 ms 166784 KB Output is correct
12 Correct 1645 ms 166784 KB Output is correct
13 Correct 1696 ms 170468 KB Output is correct
14 Correct 1707 ms 170468 KB Output is correct
15 Correct 1473 ms 170468 KB Output is correct
16 Correct 2 ms 170468 KB Output is correct
17 Correct 2 ms 170468 KB Output is correct
18 Correct 2 ms 170468 KB Output is correct
19 Correct 3 ms 170468 KB Output is correct
20 Correct 2 ms 170468 KB Output is correct
21 Correct 3 ms 170468 KB Output is correct
22 Correct 3 ms 170468 KB Output is correct
23 Correct 2 ms 170468 KB Output is correct
24 Correct 2 ms 170468 KB Output is correct
25 Correct 2 ms 170468 KB Output is correct
26 Correct 3 ms 170468 KB Output is correct
27 Correct 2 ms 170468 KB Output is correct
28 Correct 3 ms 170468 KB Output is correct
29 Correct 3 ms 170468 KB Output is correct
30 Correct 3 ms 170468 KB Output is correct
31 Correct 2 ms 170468 KB Output is correct
32 Correct 2 ms 170468 KB Output is correct
33 Correct 3 ms 170468 KB Output is correct
34 Correct 3 ms 170468 KB Output is correct
35 Correct 3 ms 170468 KB Output is correct
36 Correct 18 ms 170468 KB Output is correct
37 Correct 15 ms 170468 KB Output is correct
38 Correct 23 ms 170468 KB Output is correct
39 Correct 21 ms 170468 KB Output is correct
40 Correct 19 ms 170468 KB Output is correct
41 Correct 19 ms 170468 KB Output is correct
42 Correct 20 ms 170468 KB Output is correct
43 Correct 19 ms 170468 KB Output is correct
44 Correct 19 ms 170468 KB Output is correct
45 Correct 22 ms 170468 KB Output is correct
46 Correct 21 ms 170468 KB Output is correct
47 Correct 20 ms 170468 KB Output is correct
48 Correct 12 ms 170468 KB Output is correct
49 Correct 14 ms 170468 KB Output is correct
50 Correct 12 ms 170468 KB Output is correct
51 Correct 1646 ms 170468 KB Output is correct
52 Correct 1632 ms 170468 KB Output is correct
53 Correct 1541 ms 170468 KB Output is correct
54 Correct 1789 ms 188508 KB Output is correct
55 Correct 1707 ms 188524 KB Output is correct
56 Correct 1963 ms 188524 KB Output is correct
57 Correct 1913 ms 188524 KB Output is correct
58 Correct 1820 ms 188524 KB Output is correct
59 Correct 1654 ms 188524 KB Output is correct
60 Correct 1700 ms 188524 KB Output is correct
61 Correct 1753 ms 188524 KB Output is correct
62 Correct 1963 ms 188524 KB Output is correct
63 Correct 929 ms 188524 KB Output is correct
64 Correct 902 ms 188524 KB Output is correct
65 Correct 698 ms 188524 KB Output is correct
66 Correct 1421 ms 188852 KB Output is correct
67 Correct 1521 ms 189160 KB Output is correct
68 Correct 1742 ms 189160 KB Output is correct