Cod sursa(job #1920511)

Utilizator SirbuSirbu Ioan Sirbu Data 10 martie 2017 02:49:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define ebs 1.0/1e12

using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

struct punct {
double x;
double y;
}v[120002];

int infas[120002];
int lg,n;


bool cmp (punct a, punct b){

  if (fabs(a.x-b.x) <= ebs)
    return a.y < b.y;
  return a.x < b.x;
}

double det (punct a, punct b, punct c){
  return a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
}

void infasurare(){

  for (int i = 1; i <= n; ++i){
    while (lg > 1 && det(v[infas[lg-1]],v[infas[lg]],v[i]) <= 0)
      lg--;
    infas[++lg] = i;
  }

  int aux = lg;

  for (int i = n; i >= 1; --i){
    while (lg > aux && det(v[infas[lg-1]],v[infas[lg]],v[i]) <= 0)
      lg--;
    infas[++lg] = i;
  }
}

int main (){

  fin >> n;
  for (int i = 1; i <= n; ++i)
    fin >> v[i].x >> v[i].y;

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

  infasurare();

  fout << lg-1 << "\n";
  for (int i = 1; i < lg; ++i)
    fout << fixed << setprecision(6) << v[infas[i]].x << " " << v[infas[i]].y << "\n";


}