Submission #322323

#	Time	Username	Problem	Language	Result	Execution time	Memory
322323		lohacho	공룡 발자국 (KOI18_footprint)	C++14	14 / 100	114 ms	74832 KiB

footprint

#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 (stderr)

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 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45