Submission #146582

#	Time	Username	Problem	Language	Result	Execution time	Memory
146582		jh05013	공룡 발자국 (KOI18_footprint)	C++17	14 / 100	4 ms	508 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);}
template <class T1, class T2>ostream&operator<<(ostream &os,pair<T1,T2>const&x){os<<'('<<x.first<<", "<<x.second<<')';return os;}
template <class Ch, class Tr, class Container>basic_ostream<Ch,Tr>&operator<<(basic_ostream<Ch,Tr>&os,Container const&x){for(auto&y:x)os<<y<<" ";return os;}

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 j=1; j<n-1; j++){
        vector<int> bef, aft;
        for(int i=0; i<j; i++) bef.push_back(i);
        for(int k=j+1; k<n; 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(dp[0][i][j] && maxd <= dp[0][i][j])
                    maxd = dp[0][i][j]+1, pid = i;
                ptr++;
            }
            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(dp[1][i][j] && maxd <= dp[1][i][j])
                    maxd = dp[1][i][j]+1, pid = i;
                ptr++;
            }
            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';



    bool ccwmode = true;
    for(int i=2; i<trace.size(); i++){
        ll c = ccw(pnts[trace[i-2]], pnts[trace[i-1]], pnts[trace[i]]);
        if(ccwmode) assert(c > 0);
        else assert(c < 0);
        ccwmode = !ccwmode;
    }
}

Compilation message (stderr)

footprint.cpp: In function 'int main()':
footprint.cpp:54: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:65: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:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=2; i<trace.size(); i++){
                  ~^~~~~~~~~~~~~

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