oj.uz

Submission #322323

# Submission time Handle Problem Language Result Execution time Memory
322323 2020-11-14T13:02:22 Z lohacho None (KOI18_footprint) C++14
14 / 100
 114 ms 74832 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];
                }
                else{
                    break;
                }
                ++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:98:8: warning: 'num' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     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 110 ms 69996 KB Output is correct
2 Correct 96 ms 72428 KB Output is correct
3 Correct 105 ms 71252 KB Output is correct
4 Correct 78 ms 72812 KB Output is correct
5 Correct 81 ms 71596 KB Output is correct
6 Correct 114 ms 72588 KB Output is correct
7 Correct 77 ms 72044 KB Output is correct
8 Correct 83 ms 72812 KB Output is correct
9 Correct 78 ms 73068 KB Output is correct
10 Correct 82 ms 72812 KB Output is correct
11 Correct 95 ms 72552 KB Output is correct
12 Correct 93 ms 73124 KB Output is correct
13 Correct 107 ms 74832 KB Output is correct
14 Correct 74 ms 72684 KB Output is correct
15 Correct 74 ms 71332 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 404 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 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 1 ms 404 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 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 110 ms 69996 KB Output is correct
2 Correct 96 ms 72428 KB Output is correct
3 Correct 105 ms 71252 KB Output is correct
4 Correct 78 ms 72812 KB Output is correct
5 Correct 81 ms 71596 KB Output is correct
6 Correct 114 ms 72588 KB Output is correct
7 Correct 77 ms 72044 KB Output is correct
8 Correct 83 ms 72812 KB Output is correct
9 Correct 78 ms 73068 KB Output is correct
10 Correct 82 ms 72812 KB Output is correct
11 Correct 95 ms 72552 KB Output is correct
12 Correct 93 ms 73124 KB Output is correct
13 Correct 107 ms 74832 KB Output is correct
14 Correct 74 ms 72684 KB Output is correct
15 Correct 74 ms 71332 KB Output is correct
16 Correct 1 ms 404 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Incorrect 1 ms 364 KB Output isn't correct
20 Halted 0 ms 0 KB -