Cod sursa(job #1160929)

Utilizator thebest001Neagu Rares Florian thebest001 Data 30 martie 2014 21:57:37
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 100001

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

struct pereche {
double x,y;
};
pereche v[MAX];
pereche infasuratoare[MAX];
int infasuratoareN = 0;

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


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

  pereche temp = v[1];
  v[1] =  v[minI];
  v[minI] = temp;

  sort(v + 2, v + n + 1, cmp);

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

  out<<fixed<<infasuratoareN<<"\n";
  for (int i = infasuratoareN; i >= 1; i--)
    out<<setprecision(9)<<infasuratoare[i].x<<" "<<infasuratoare[i].y<<"\n";

  return 0;
}