Submission #146656

#	Time	Username	Problem	Language	Result	Execution time	Memory
146656		jh05013	공룡 발자국 (KOI18_footprint)	C++17	100 / 100	1273 ms	111096 KiB

footprint

#include <bits/stdc++.h>
#define entire(X) X.begin(),X.end()
#define LAMB [](point const &a, point const &b)->bool
#define LAMBI [&j](int const &a, int 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;});

    // base case
    for(int i=1; i<n; i++) dp[0][0][i] = 2; // 0 = heel
    // update
    for(int j=1; j<n-1; j++){
        vector<int> bef, aft;
        for(int i=0; i<j; i++)
            if(!i || ccw(pnts[0], pnts[i], pnts[j])) bef.push_back(i);
        for(int k=j+1; k<n; k++)
            if(ccw(pnts[0], pnts[j], pnts[k])) aft.push_back(k);
        sort(entire(bef), LAMBI{return ccw(pnts[j], pnts[a], pnts[b]) > 0;});
        sort(entire(aft), LAMBI{return ccw(pnts[j], pnts[a], pnts[b]) > 0;});
        int ptr = 0, maxd = 0, pid = 0;
        for(int k: aft){
            while(ptr<bef.size() && ccw(pnts[j], pnts[k], pnts[bef[ptr]]) > 0){
                int i = bef[ptr++];
                if(maxd <= dp[0][i][j]) maxd = dp[0][i][j]+1, pid = i;
            }
            dp[1][j][k] = maxd, prv[1][j][k] = pid;
        }
        reverse(entire(bef)), reverse(entire(aft));
        ptr = maxd = pid = 0;
        for(int k: aft){
            while(ptr<bef.size() && ccw(pnts[j], pnts[k], pnts[bef[ptr]]) < 0){
                int i = bef[ptr++];
                if(maxd <= dp[1][i][j]) maxd = dp[1][i][j]+1, pid = i;
            }
            dp[0][j][k] = maxd, prv[0][j][k] = pid;
        }
    }

    // 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';
}

Compilation message (stderr)

footprint.cpp: In function 'int main()':
footprint.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(ptr<bef.size() && ccw(pnts[j], pnts[k], pnts[bef[ptr]]) > 0){
                   ~~~^~~~~~~~~~~
footprint.cpp:56:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(ptr<bef.size() && ccw(pnts[j], pnts[k], pnts[bef[ptr]]) < 0){
                   ~~~^~~~~~~~~~~

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