oj.uz

Submission #471551

# Submission time Handle Problem Language Result Execution time Memory
471551 2021-09-09T17:54:26 Z gs18103 None (KOI18_footprint) C++17
14 / 100
 42 ms 34628 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 33096 KB Output is correct
2 Correct 39 ms 33912 KB Output is correct
3 Correct 38 ms 33508 KB Output is correct
4 Correct 40 ms 33916 KB Output is correct
5 Correct 38 ms 33684 KB Output is correct
6 Correct 39 ms 34000 KB Output is correct
7 Correct 39 ms 33800 KB Output is correct
8 Correct 41 ms 34044 KB Output is correct
9 Correct 42 ms 34116 KB Output is correct
10 Correct 40 ms 33988 KB Output is correct
11 Correct 39 ms 34012 KB Output is correct
12 Correct 41 ms 34176 KB Output is correct
13 Correct 40 ms 34628 KB Output is correct
14 Correct 40 ms 33936 KB Output is correct
15 Correct 39 ms 33604 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 1 ms 332 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 332 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 33096 KB Output is correct
2 Correct 39 ms 33912 KB Output is correct
3 Correct 38 ms 33508 KB Output is correct
4 Correct 40 ms 33916 KB Output is correct
5 Correct 38 ms 33684 KB Output is correct
6 Correct 39 ms 34000 KB Output is correct
7 Correct 39 ms 33800 KB Output is correct
8 Correct 41 ms 34044 KB Output is correct
9 Correct 42 ms 34116 KB Output is correct
10 Correct 40 ms 33988 KB Output is correct
11 Correct 39 ms 34012 KB Output is correct
12 Correct 41 ms 34176 KB Output is correct
13 Correct 40 ms 34628 KB Output is correct
14 Correct 40 ms 33936 KB Output is correct
15 Correct 39 ms 33604 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 324 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Incorrect 1 ms 332 KB Output isn't correct
20 Halted 0 ms 0 KB -