Cod sursa(job #3226627)

Utilizator vladburacBurac Vlad vladburac Data 22 aprilie 2024 12:42:25
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pll pair<long long, long long>
using ll = long long;
const int VALMAX = 1e6 + 1e3;
const int LOGMAX = 18;
const int INF = 1e9;
const int NMAX = 120e3 + 1;
const double EPS = 0.000005;
const int IDK = 1e6 * 20 + 5;
mt19937 rnd( chrono::steady_clock::now().time_since_epoch().count() );


//#ifndef HOME
  ifstream fin( "infasuratoare.in" );
  ofstream fout( "infasuratoare.out" );
  #define cin fin
  #define cout fout
//#endif // HOME

struct Point{
  double x, y;
};
Point points[NMAX];
vector<Point> st;
int n;

// < 0 => trigonometric
// > 0 => invers trigonometric
// = 0 => coliniare
double orientation( Point a, Point b, Point c ) {
  return ( b.y - a.y ) * ( c.x - b.x ) - ( b.x - a.x ) * ( c.y - b.y );
}

void construct( int semn, vector<Point>&ans ) {
  int i;
  st.clear();
  st.push_back( points[0] );
  for( i = 1; i < n; i++ ) {
    while( st.size() >= 2 && orientation( st.end()[-2], st.end()[-1], points[i] ) * semn <= 0 )
      st.pop_back();
    st.push_back( points[i] );
  }
  for( i = 1; i < st.size() - 1; i++ )
    ans.push_back( st[i] );
}

vector <Point> top;
vector <Point> bottom;
void solve() {
  int i;
  cin >> n;
  for( i = 0; i < n; i++ )
    cin >> points[i].x >> points[i].y;
  sort( points, points + n, []( Point& a, Point& b ) {
      return a.x < b.x || ( a.x == b.x && a.y > b.y );
  } );
  Point first = points[0];
  Point last = points[n-1];
  construct( 1, top );
  construct( -1, bottom );

  cout << fixed << setprecision( 12 );
  cout << 2 + top.size() + bottom.size() << "\n";
  cout << first.x << " " << first.y << "\n";
  for( auto p: bottom )
    cout << p.x << " " << p.y << "\n";
  cout << last.x << " " << last.y << "\n";
  reverse( top.begin(), top.end() );
  for( auto p: top )
    cout << p.x << " " << p.y << "\n";
}
int main() {
  //ios_base::sync_with_stdio( false );
  //cin.tie( NULL );
  //cout.tie( NULL );
  int t = 1;
  // cin >> t;
  while( t-- )
    solve();
}