Cod sursa(job #1156393)

Utilizator thebest001Neagu Rares Florian thebest001 Data 27 martie 2014 17:10:08
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 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(pereche a,pereche b,pereche c){
  return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

int cmp(pair<double, double> a,pair<double, double> b) {
  return cross(*v.begin(), a, b) < 0;
}

vector<pereche> infasuratoare;

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);

  infasuratoare.push_back(*(v.begin()));
  infasuratoare.push_back(*(v.begin() + 1));

  for (vector<pereche>::iterator i = v.begin() + 2; i != v.end(); i++) {
    while (infasuratoare.size() >= 2 && cross(*(infasuratoare.end() - 2), *(infasuratoare.end() - 1), *i) > 0) {
      infasuratoare.pop_back();
    }
    infasuratoare.push_back(*i);
  }

  out<<fixed<<infasuratoare.size()<<"\n";
  for (vector<pereche>::reverse_iterator i = infasuratoare.rbegin(); i != infasuratoare.rend(); i++) {

    out<<setprecision(9)<<i->x<<" "<<i->y<<"\n";
  }

  return 0;
}