Submission #1088640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088640		gs25	공룡 발자국 (KOI18_footprint)	C++17	14 / 100	46 ms	704 KiB

footprint

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#include <chrono> 
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, n) for (int i = 1; i <= n; ++i)
#define x first
#define y second
using namespace std;
typedef long long ll;

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V> void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ", ";
  __print(x.second);
  cerr << '}';
}
template <typename T> void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x)
    cerr << (f++ ? ", " : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v))
    cerr << ", ";
  _print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...)                                                              \
  cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = [";    \
  _print(x);                                                                   \
  cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll randint(ll lb, ll ub) { return uniform_int_distribution<ll>(lb, ub)(rng); }

typedef pair<long long,long long> pll; 
// a -> b -> c ccw? 
int ccw(pair<ll,ll> a, pair<ll,ll> b, pair<ll,ll> c){
  ll tmp = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
  return (tmp>0) - (tmp<0); 
}

ll dist(pll a, pll b){
  return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); 
}

int dp[3010], dp1[3010], bitch[3010]; 

void solve(){
  int n; 
  vector<pll> v; 
  cin >> n; 
  rep(i,n){
    int a,b; cin >> a >> b; 
    v.pb({a,b}); 
  }
  sort(v.begin(),v.end(),[](auto a, auto b){
    return a.y < b.y; 
  });
  auto fuck = v[0]; 
  sort(v.begin()+1,v.end(),[&](auto a, auto b){
    int ff = ccw(fuck,a,b); 
    if(ff!=0) return ff<0; 
    return dist(a,fuck) < dist(b,fuck); 
  });
  dbg(v)
  for(int i=1; i<n; ){
    int j = i; 
    int dpM = 0, mk = i-1; 
    while(j<n && ccw(fuck,v[i],v[j])==0) j++; 
    if(i==1){
      i=j; continue; 
    }
    for(int k=i-1; k>=1; k--){
      int tt = ccw(v[j-1],v[mk],v[k]); 
      if(tt>0){
        mk = k; 
      }
      if(tt<0){
        if(dp[k]+2>dpM){
          bitch[j-1] = mk; 
          dpM = dp[k]+2; 
          dp[j-1] = dpM; 
          dp1[j-1] = k; 
        }
      }
    }
    i=j; 
  }
  int M = 0,midx = -1; 
  for(int i=1; i<n; i++){
    if(dp[i]>M) M = dp[i], midx = i; 
  }
  if(M==0){
    cout << 0; return; 
  }
  cout << M+2 << "\n"; 
  vector<int> ans; 
  ans.pb(0); 
  int st = midx; 
  while(1){
    if(dp[st]==0){
      ans.pb(st); break; 
    }
    ans.pb(st); 
    ans.pb(bitch[st]); 
    st = dp1[st]; 
  }
  for(auto i : ans) cout << v[i].x << " " << v[i].y << "\n"; 
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
  // cin >> t;
  while(t--) solve(); 
  return 0;
}

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