Cod sursa(job #1159907)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 29 martie 2014 22:53:32
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <queue>
using namespace std;

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



typedef pair<double, double> pereche;
vector<pereche> v;
#define x first
#define y second
double cross(const pereche &a ,const pereche &b, const pereche &c){
  return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

int cmp(const pereche &a, const pereche &b) {
  return cross(v[0], a, b) < 0;
}

pereche infasuratoare[120005];

int main() {
  int n;
  in>>n;
  double minX=1e10, minI = 1;
  for (int i = 1; i <= n; i++) {
    pereche p;
    in>>p.x>>p.y;
    if (minX > p.x) {
      minX = p.x;
      minI = i;
    }
    v.push_back(p);
  }

  iter_swap(v.begin() + minI - 1, v.begin());

  sort(v.begin() + 1, v.end(), cmp);

  int K=1;
  infasuratoare[0]=v[0];
  infasuratoare[0]=v[1];

  for (int i =2; i < n; ++i) {
    while (K>= 1 && cross(infasuratoare[K-1],infasuratoare[K], v[i]) > 0) --K;
    infasuratoare[++K]=v[i];
  }

  out<<fixed<<K<<"\n";
  for(int i=K;i ; --i)

    out<<setprecision(9)<<infasuratoare[i].x<<" "<<infasuratoare[i].x<<"\n";

  return 0;
}