Cod sursa(job #3237864)

Utilizator tsg38Tsg Tsg tsg38 Data 13 iulie 2024 20:28:10
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;
 
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
 
const int MAXN = 12e4 + 1;
 
struct Point {
  double x, y;
} p[MAXN];

inline double det( Point a, Point b, Point c ) {
  return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

int main() {
  int n, idx = 2;
  
  fin >> n;
  for ( int i = 0; i < n; ++i ) {
    fin >> p[i].x >> p[i].y;
  }
  sort( p, p + n, []( const Point &a, const Point &b ) { 
    return (a.x < b.x) || (a.x == b.x && a.y < b.y);	
  });
  
  sort( p + 1, p + n, []( const Point &a, const Point &b ){
	return det(p[0], a, b) > 0;
  });
  
  vector<int> stk{0, 1};
  while ( idx < n ) {
    while ( stk.size() > 1 && det(p[stk.back()], p[stk[stk.size() - 2]], p[idx]) > 0 ) {
      stk.pop_back();
	}
    stk.push_back(idx++);
  }
  fout << stk.size() << "\n" << setprecision(6) << fixed;
  for ( auto i : stk ) {
    fout << p[i].x << " " << p[i].y << "\n"; 	
  }
  fin.close();
  fout.close();
  return 0;
}