oj.uz

Submission #322310

# Submission time Handle Problem Language Result Execution time Memory
322310 2020-11-14T12:39:09 Z lohacho None (KOI18_footprint) C++14
14 / 100
 90 ms 74636 KB 
#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const LL MOD = (LL)1e9 + 7;
const LL NS = (LL)3004;
LL N;
pair<LL, LL> a[NS];
pair<LL, LL> mid[NS][NS];
LL dp[NS], from[NS];

inline LL ccw(pair<LL, LL> A, pair<LL, LL> B, pair<LL, LL> C){
    B.first -= A.first, C.first -= A.first;
    B.second -= A.second, C.second -= A.second;
    LL val = B.first * C.second - B.second * C.first;
    if(val > 0) return 1;
    if(val < 0) return -1;
    return 0;
}

void out(LL x){
    if(x == 1){
        cout << a[x].first << ' ' << a[x].second << '\n';
        return;
    }
    out(from[x]);
    if(from[x] != 1){
        cout << mid[from[x]][x].first << ' ' << mid[from[x]][x].second << '\n';
    }
    cout << a[x].first << ' ' << a[x].second << '\n';
}

int main(){
//    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    LL low = MOD, pos;
    for(LL i = 1; i <= N; ++i){
        cin >> a[i].first >> a[i].second;
        if(a[i].second < low){
            low = a[i].second;
            pos = i;
        }
    }
    swap(a[1], a[pos]);
    sort(a + 2, a + N + 1, [&](pair<LL, LL> A, pair<LL, LL> B){return ccw(a[1], A, B) > 0;});
    for(LL i = 2; i <= N; ++i){
        LL x = i + 1;
        pair<LL, LL> pos = {MOD, MOD};
        for(LL j = i + 2; j <= N; ++j){
            while(x <= N && ccw(a[1], a[x], a[i]) == 0){
                ++x;
            }
            while(x < j && ccw(a[1], a[x], a[j]) > 0){
                if(pos.first == MOD){
                    pos = a[x];
                }
                else if(ccw(a[i], pos, a[x]) > 0){
                    pos = a[x];
                }
                ++x;
            }
            mid[i][j] = {MOD, MOD};
            if(pos.first != MOD && ccw(a[i], pos, a[j]) < 0){
                mid[i][j] = pos;
            }
        }
    }
    LL mx = 0, num;
    for(LL i = 2; i <= N; ++i){
        if(!dp[i]){
            dp[i] = 2;
            from[i] = 1;
        }
        for(LL j = i + 2; j <= N; ++j){
            if(mid[i][j].first != MOD){
                if(dp[i] + 2 > dp[j]){
                    dp[j] = dp[i] + 2;
                    from[j] = i;
                }
            }
        }
        if(dp[i] > mx){
            mx = dp[i];
            num = i;
        }
    }
    if(mx == 2){
        cout << 0;
        return 0;
    }
    cout << mx << '\n';
    out(num);
    return 0;
}

Compilation message

footprint.cpp: In function 'int main()':
footprint.cpp:95:8: warning: 'num' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |     out(num);
      |     ~~~^~~~~
footprint.cpp:39:19: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |     LL low = MOD, pos;
      |                   ^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 69996 KB Output is correct
2 Correct 87 ms 72556 KB Output is correct
3 Correct 83 ms 71148 KB Output is correct
4 Correct 86 ms 72556 KB Output is correct
5 Correct 86 ms 71660 KB Output is correct
6 Correct 88 ms 72556 KB Output is correct
7 Correct 87 ms 72044 KB Output is correct
8 Correct 87 ms 72812 KB Output is correct
9 Correct 90 ms 72940 KB Output is correct
10 Correct 88 ms 72812 KB Output is correct
11 Correct 85 ms 72556 KB Output is correct
12 Correct 86 ms 73132 KB Output is correct
13 Correct 87 ms 74636 KB Output is correct
14 Correct 86 ms 72556 KB Output is correct
15 Correct 83 ms 71276 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 69996 KB Output is correct
2 Correct 87 ms 72556 KB Output is correct
3 Correct 83 ms 71148 KB Output is correct
4 Correct 86 ms 72556 KB Output is correct
5 Correct 86 ms 71660 KB Output is correct
6 Correct 88 ms 72556 KB Output is correct
7 Correct 87 ms 72044 KB Output is correct
8 Correct 87 ms 72812 KB Output is correct
9 Correct 90 ms 72940 KB Output is correct
10 Correct 88 ms 72812 KB Output is correct
11 Correct 85 ms 72556 KB Output is correct
12 Correct 86 ms 73132 KB Output is correct
13 Correct 87 ms 74636 KB Output is correct
14 Correct 86 ms 72556 KB Output is correct
15 Correct 83 ms 71276 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Incorrect 1 ms 364 KB Output isn't correct
20 Halted 0 ms 0 KB -