Submission #1066306

#TimeUsernameProblemLanguageResultExecution timeMemory
1066306Serendipity__공룡 발자국 (KOI18_footprint)C++17
100 / 100
802 ms114004 KiB
/*############################################################################################################### ## Author : Kim Tae Yoon (Serendipity__) ## ###############################################################################################################*/ #include <bits/stdc++.h> #define fastio std::ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define prntyes cout<<"Yes\n"; #define prntno cout<<"No\n"; using namespace std; // mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); // random int64 generator typedef long long ll; typedef unsigned long ul; typedef unsigned long long ull; typedef __int128 ll128; typedef long double ld; typedef pair<int, int> pi; typedef pair<ll, ll> pii; typedef complex<double> inum; // Macros from KACTL pdf #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef vector<int> vi; typedef vector<double> vd; const double PI = acos(-1); const int INF = 0x3f3f3f3f; const ll LLINF = 1000000000000000000LL; const ll MAX = 200005; // depending on the problem const ll MOD = 998244353; // depending on the problem template <class T> int sgn(T x) { return (x > 0) - (x < 0); } template<class T> struct Point { typedef Point P; T x, y; explicit Point(T x=0, T y=0) : x(x), y(y) {} bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); } bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } P operator+(P p) const { return P(x+p.x, y+p.y); } P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(T d) const { return P(x*d, y*d); } P operator/(T d) const { return P(x/d, y/d); } T dot(P p) const { return x*p.x + y*p.y; } T cross(P p) const { return x*p.y - y*p.x; } T cross(P a, P b) const { return (a-*this).cross(b-*this); } T dist2() const { return x*x + y*y; } double dist() const { return sqrt((double)dist2()); } // angle to x-axis in interval [-pi, pi] double angle() const { return atan2(y, x); } P unit() const { return *this/dist(); } // makes dist()=1 P perp() const { return P(-y, x); } // rotates +90 degrees P normal() const { return perp().unit(); } // returns point rotated 'a' radians ccw around the origin P rotate(double a) const { return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); } friend ostream& operator<<(ostream& os, P p) { return os << "(" << p.x << "," << p.y << ")"; } }; typedef Point<ll> P; int dp[2][3005][3005]; int track[2][3005][3005]; void solve() { ll N; cin>>N; vector<P> A(N); for (int i=0;i<N;i++){ ll x,y; cin>>x>>y; A[i] = P(x,y); } int s = 0; for (int i=1;i<N;i++){ if (A[i].y < A[s].y){ s = i; } } swap(A[0], A[s]); ll dx,dy; dx = A[0].x; dy = A[0].y; for (int i=0;i<N;i++){ A[i].x -= dx; A[i].y -= dy; } sort(A.begin()+1, A.end(), [&](P l, P r){ return l.cross(r) > 0; }); for (int j=N-1;j>=1;j--){ vector<int> L,R; for (int i=0;i<N;i++){ if (A[j].cross(A[i]) > 0){ L.push_back(i); }else if (A[j].cross(A[i]) < 0){ R.push_back(i); } } sort(L.begin(), L.end(), [&](int l, int r){ return A[j].cross(A[l],A[r]) > 0; }); sort(R.begin(), R.end(), [&](int l, int r){ return A[j].cross(A[l],A[r]) > 0; }); int ls = L.size(); int rs = R.size(); int p; // ccw = 0 p = 0; int mx = -INF; int pos = -1; for (int t=0;t<rs;t++){ int i = R[t]; while(p<ls){ int k = L[p]; if (A[j].cross(A[i],A[k]) > 0){ if (mx < dp[1][k][j]+1){ mx = dp[1][k][j]+1; pos = k; } ++p; }else{ break; } } dp[0][j][i] = mx; track[0][j][i] = pos; } // ccw = 1 p = ls-1; mx = 2; pos = -1; for (int t=rs-1;t>=0;t--){ int i = R[t]; while(p>=0){ int k = L[p]; if (A[j].cross(A[i],A[k]) < 0){ if (mx < dp[0][k][j]+1){ mx = dp[0][k][j]+1; pos = k; } --p; }else{ break; } } dp[1][j][i] = mx; track[1][j][i] = pos; } } int ans = 0; int s1,s2,t=0; for (int i=1;i<N;i++){ for (int j=i+1;j<N;j++){ if (dp[0][j][i]+1 > ans){ ans = dp[0][j][i]+1; s1 = j; s2 = i; } } } if (ans < 4){cout<<0; return;} for (int i=0;i<N;i++){ A[i].x += dx; A[i].y += dy; } cout<<ans<<"\n"; cout<<A[0].x<<" "<<A[0].y<<"\n"; cout<<A[s2].x<<" "<<A[s2].y<<"\n"; while(1){ if (s1==-1){break;} cout<<A[s1].x<<" "<<A[s1].y<<"\n"; tie(s1,s2) = pi(track[t][s1][s2],s1); t^=1; } } int main() { fastio; int tc = 1; // cin >> tc; while (tc--) { solve(); } return 0; }

Compilation message (stderr)

footprint.cpp: In function 'void solve()':
footprint.cpp:178:15: warning: 's2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  178 |     cout<<A[s2].x<<" "<<A[s2].y<<"\n";
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...