Cod sursa(job #2628262)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 15 iunie 2020 11:52:14
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
//
//  main.cpp
//  infasuratoare convexa
//
//  Created by she on 15/06/2020.
//  Copyright © 2020 Eusebiu Rares. All rights reserved.
//

#include <iostream>
#include "fstream"
#include "iomanip"
#include "algorithm"
#include "vector"
 
std::fstream in("infasuratoare.in", std::ios::in) ;
std::fstream out("infasuratoare.out", std::ios::out) ;
 
int const nmax = 120000 ;
 
struct Point {
  double x ;
  double y ;
  bool operator < (Point &a) const {
		if(y != a.y) {
      return y < a.y ;
		}
		return x < a.x ;
  }
};
 
Point v[1 + nmax] ;
 
double determinant(Point a, Point b, Point c) {
  double plus  = a.x * b.y + a.y * c.x + b.x * c.y ;
  double minus = b.y * c.x + a.y * b.x + a.x * c.y ;
  return (plus - minus) ;
}
 
int main() {
  int n ;
  in >> n ;
  int lowestPoint(1) ;
  for(int i = 1  ; i <= n ; i++){
    in >> v[i].x >> v[i].y ;
    if(v[i] < v[lowestPoint]){
      lowestPoint = i ;
    }
  }
  std::swap(v[1] , v[lowestPoint]) ;
	std::sort(v + 2 , v + n + 1 , [](Point a, Point b) {
		return (0 <= determinant(v[1] , a , b)) ;
	}) ;
	std::vector <int> hull ;
  hull.push_back(1) ; hull.push_back(2) ; hull.push_back(3) ;
  for(int i = 4  ; i <= n  ; ++ i){
    while(determinant(v[hull[hull.size() - 2]], v[hull[hull.size() - 1]], v[i]) < 0){
      hull.pop_back() ;
    }
    hull.push_back(i) ;
  }
  out << hull.size() << '\n' ;
	out << std::setprecision(6) << std::fixed ;
  for(auto point : hull){
    out << v[point].x << " " << v[point].y << '\n' ;
  }
}