Submission #234640

#	Time	Username	Problem	Language	Result	Execution time	Memory
234640		knon0501	공룡 발자국 (KOI18_footprint)	C++14	14 / 100	22 ms	760 KiB

footprint

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
typedef pair<ll,ll> pp;
pp a[3005];
int dp[3005];
pp p[3005];
int ccw(pp q,pp w,pp e){
    ll s=(w.x-q.x)*(e.y-w.y)-(w.y-q.y)*(e.x-w.x);
    if(s>0)return 1;
    if(s==0)return 0;
    if(s<0)return -1;
}
int n;
ll dist(pp q,pp w){
    return (q.x-w.x)*(q.x-w.x)+(q.y-w.y)*(q.y-w.y);
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n;
    int i;
    int k=1;
    for(i=1 ; i<=n ; i++){
        cin>>a[i].x>>a[i].y;
        if(a[i].y<a[k].y)k=i;
    }

    swap(a[k],a[1]);
    sort(a+2,a+n+1,[&](pp q,pp w){ll s=ccw(a[1],q,w);
        if(s==0)return dist(a[1],q)<dist(a[1],w);
        else return s>0;});
   // for(i=1 ; i<=n ; i++)cout<<a[i].x<<" "<<a[i].y<<endl;
    k=0;
    for(i=2 ; i<=n ; i++)dp[i]=1;
    for(i=2 ; i<=n ; i++){

        int t=i+1;
        if(dp[i]>dp[k])k=i;
        for(int j=i+2 ; j<=n ; j++){
            if(ccw(a[1],a[t],a[j])!=0 && ccw(a[1],a[t],a[i])!=0 && ccw(a[i],a[t],a[j])<0){
                if(dp[i]+1>dp[j]){
                    dp[j]=dp[i]+1;
                    p[j]={i,t};
                }
            }
            else if(ccw(a[i],a[t],a[j])>0)t=j;
        }
    }

    if(dp[k]<=1){
        cout<<0;
        return 0;
    }
    vector<pp> b;
    cout<<2*dp[k]<<"\n";
    cout<<a[1].x<<" "<<a[1].y<<"\n";

    while(k>0){
        b.push_back(a[k]);
        if(p[k].second>0)
            b.push_back(a[p[k].second]);
        k=p[k].first;
    }
    reverse(b.begin(),b.end());
    for(auto i: b)cout<<i.x<<" "<<i.y<<"\n";
    return 0;
}

Compilation message (stderr)

footprint.cpp: In function 'int ccw(pp, pp, pp)':
footprint.cpp:15:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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