Cod sursa(job #1996659)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 2 iulie 2017 12:13:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>

using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

int const nmax = 120000;

struct Point {
  double x;
  double y;

  bool operator < (Point a) const {
    //pe varena vei face tot asa, numai ca functia va fi usor diferita
    if(y != a.y)
      return y < a.y;
    else
      return x < a.x;
  }
};

Point v[1 + nmax];

//|a.x a.y 1|a.x a.y 1
//|b.x b.y 1|b.x b.y 1
//|c.x c.y 1|c.x c.y 1
double det3(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);
}

bool compare(Point a, Point b){
  return (0 <  det3(v[1] , a , b));
}

vector <int> st;

int main() {
  int n;
  in >> n;
  int imin = 1;
  for(int i = 1 ; i <= n; i++){
    in >> v[i].x >> v[i].y;
    if(v[i] < v[imin]){
      imin = i;
    }
  }
  swap(v[1] , v[imin]);
  sort(v + 2 , v + n + 1 , compare);
  st.push_back(1);
  st.push_back(2);
  st.push_back(3);
  for(int i = 4 ; i <= n ;i++){
    while(det3(v[st[st.size() - 2]], v[st[st.size() - 1]], v[i]) < 0){
      st.pop_back();
    }
    st.push_back(i);
  }
  out<<st.size()<<'\n';
  out<<setprecision(6)<<fixed;
  for(int i = 0 ; i < st.size() ;i++){
    out<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
  }

  return 0;
}