Submission #471551

#	Time	Username	Problem	Language	Result	Execution time	Memory
471551		gs18103	공룡 발자국 (KOI18_footprint)	C++17	14 / 100	42 ms	34628 KiB

footprint

#include <bits/stdc++.h>
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 3030;
const int INF = 1e9;
const ll LINF = 9e18;

vector <pll> arr;

ll ccw(pll a, pll b, pll c) {
    return (b.fi - a.fi) * (c.se - a.se) - (b.se - a.se) * (c.fi - a.fi);
}

ll dist(pll a, pll b) {
    return (a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se);
}

bool chk[MAX][MAX];
int mid[MAX][MAX];
int dp[MAX], pre[MAX];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n;
    cin >> n;
    arr.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i].fi >> arr[i].se;
    }
    sort(all(arr), [](pll a, pll b) {
        return a.se < b.se;
    });
    sort(next(arr.begin()), arr.end(), [&](pll a, pll b) {
        if(ccw(arr[0], a, b) == 0) return dist(a, arr[0]) > dist(b, arr[0]);
        return ccw(arr[0], a, b) > 0;
    });

    for(int i = 1; i < n; i++) {
        int idx = i, mnidx;
        while(idx < n && ccw(arr[0], arr[i], arr[idx]) == 0) idx++;
        mnidx = idx;
        for(int j = idx + 1; j < n; j++) {
            if(ccw(arr[i], arr[mnidx], arr[j]) < 0) chk[i][j] = true, mid[i][j] = mnidx;
            else mnidx = j;
        }
    }

    int mx = 0, idx;
    for(int i = 1; i < n; i++) {
        dp[i] = 1;
        pre[i] = -1;
        for(int j = 1; j < i; j++) {
            if(chk[j][i]) {
                if(dp[i] <= dp[j] + 1) {
                    pre[i] = j;
                    dp[i] = dp[j] + 1;
                }
            }
        }
        if(mx < dp[i]) {
            mx = dp[i];
            idx = i;
        }
    }
    if(mx <= 1) cout << 0 << endl;
    else {
        vector <pll> ans;
        while(idx != -1) {
            ans.eb(arr[idx]);
            if(pre[idx] != -1) ans.eb(arr[mid[pre[idx]][idx]]);
            idx = pre[idx];
        }
        reverse(all(ans));
        cout << ans.size() + 1 << '\n';
        cout << arr[0].fi << ' ' << arr[0].se << '\n';
        for(auto i : ans) {
            cout << i.fi << ' ' << i.se << '\n';
        }
    }   
}

Compilation message (stderr)

footprint.cpp: In function 'int main()':
footprint.cpp:80:27: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |             ans.eb(arr[idx]);
      |                           ^

• Subtask 1: 14 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45