Submission #146581

#	Time	Username	Problem	Language	Result	Execution time	Memory
146581		jh05013	공룡 발자국 (KOI18_footprint)	C++17	55 / 100	33 ms	5752 KiB

footprint

#include <bits/stdc++.h>
#define entire(X) X.begin(),X.end()
#define LAMB [](point const &a, point const &b)->bool
using namespace std; typedef long long ll;
void OJize(){cin.tie(NULL); ios_base::sync_with_stdio(false);}

struct point{
    ll x, y;
    point(ll x, ll y): x{x}, y{y} {}
};
ostream &operator<<(ostream &os, point const &p){
    return os << p.x << ' ' << p.y;
}

// positive -> ccw; negative -> cw; 0 -> collinear
ll ccw(point a, point b, point c){
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}

int dp[2][3003][3003];
int prv[2][3003][3003];
vector<point> pnts;

int main(){OJize();
    int n; cin>>n;
    for(int i=0; i<n; i++){
        ll x, y; cin>>x>>y;
        pnts.push_back(point(x, y));
    }
    sort(entire(pnts), LAMB{return a.y < b.y;});
    sort(pnts.begin()+1, pnts.end(), LAMB{return ccw(pnts[0], a, b) > 0;});

    // subtask 1
    if(n > 300){
        cout << n << '\n';
        for(auto &p: pnts) cout<<p<<'\n';
        return 0;
    }

    // base case
    for(int i=1; i<n; i++) dp[0][0][i] = 2; // 0 = heel
    // update
    for(int i=0; i<n; i++) for(int j=i+1; j<n; j++){
        // last edge is i->j
        for(int k=j+1; k<n; k++){
            if(ccw(pnts[j], pnts[k], pnts[0]) == 0) continue;
            ll dr = ccw(pnts[i], pnts[j], pnts[k]);
            if(dr < 0 && dp[0][j][k] <= dp[1][i][j] && dp[1][i][j])
                dp[0][j][k] = dp[1][i][j]+1, prv[0][j][k] = i;
            if(dr > 0 && dp[1][j][k] <= dp[0][i][j] && dp[0][i][j])
                dp[1][j][k] = dp[0][i][j]+1, prv[1][j][k] = i;
        }
    }

    // answer
    int ans = 0, ai = 0, aj = 0;
    for(int i=1; i<n; i++) for(int j=i+1; j<n; j++){
        if(ccw(pnts[i], pnts[j], pnts[0]) <= 0) continue;
        if(ans < dp[0][i][j]) ans = dp[0][i][j], ai = i, aj = j;
    }
    if(ans == 0){cout << 0; return 0;}
    vector<int> trace = {aj, ai};
    while(trace.back()){
        int sz = trace.size();
        trace.push_back(prv[sz%2][trace[sz-1]][trace[sz-2]]);
    }
    reverse(entire(trace));

    cout<<trace.size()<<'\n';
    for(int x: trace) cout<<pnts[x]<<'\n';
}

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