Cod sursa(job #1439138)

Utilizator S7012MYPetru Trimbitas S7012MY Data 21 mai 2015 16:18:44
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#define DN 120005
#define x first
#define y second
using namespace std;

typedef pair<double,double> per;

int n;
per p[DN];
vector<per> ic;

int id(per a,per b,per c) {
  double sm=b.x*c.y+c.x*a.y+a.x*b.y;
  double df=c.x*b.y+a.x*c.y+b.x*a.y;
  return sm-df<0;
}

int main() {
  ifstream f("infasuratoare.in");
  ofstream g("infasuratoare.out");
  f>>n;
  for(int i=0; i<n; ++i) f>>p[i].x>>p[i].y;
  sort(p,p+n);
  ic.push_back(p[0]); ic.push_back(p[1]);
  for(int i=2; i<n; ++i) {
    for(;ic.size()>1 && id(ic[ic.size()-2],ic.back(),p[i]); ic.pop_back());
    ic.push_back(p[i]);
  }
  for(int i=n-2; i>=0; --i) {
    for(;ic.size()>1 && id(ic[ic.size()-2],ic.back(),p[i]); ic.pop_back());
    ic.push_back(p[i]);
  }
  ic.pop_back();
  g<<ic.size()<<'\n';
  for(int i=0; i<ic.size(); ++i) g<<fixed<<setprecision(9)<<p[i].x<<' '<<p[i].y<<'\n';
  //cout<<id(make_pair(0,0),make_pair(1,0),make_pair(1,1));
}