oj.uz

Submission #1088640

# Submission time Handle Problem Language Result Execution time Memory
1088640 2024-09-14T17:31:35 Z gs25 None (KOI18_footprint) C++17
14 / 100
 46 ms 704 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 704 KB Output is correct
2 Correct 42 ms 604 KB Output is correct
3 Correct 27 ms 660 KB Output is correct
4 Correct 27 ms 640 KB Output is correct
5 Correct 27 ms 600 KB Output is correct
6 Correct 27 ms 648 KB Output is correct
7 Correct 26 ms 688 KB Output is correct
8 Correct 46 ms 600 KB Output is correct
9 Correct 27 ms 600 KB Output is correct
10 Correct 27 ms 688 KB Output is correct
11 Correct 27 ms 604 KB Output is correct
12 Correct 27 ms 600 KB Output is correct
13 Correct 30 ms 600 KB Output is correct
14 Correct 26 ms 600 KB Output is correct
15 Correct 26 ms 600 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 704 KB Output is correct
2 Correct 42 ms 604 KB Output is correct
3 Correct 27 ms 660 KB Output is correct
4 Correct 27 ms 640 KB Output is correct
5 Correct 27 ms 600 KB Output is correct
6 Correct 27 ms 648 KB Output is correct
7 Correct 26 ms 688 KB Output is correct
8 Correct 46 ms 600 KB Output is correct
9 Correct 27 ms 600 KB Output is correct
10 Correct 27 ms 688 KB Output is correct
11 Correct 27 ms 604 KB Output is correct
12 Correct 27 ms 600 KB Output is correct
13 Correct 30 ms 600 KB Output is correct
14 Correct 26 ms 600 KB Output is correct
15 Correct 26 ms 600 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Halted 0 ms 0 KB -