Cod sursa(job #1242910)

Utilizator S7012MYPetru Trimbitas S7012MY Data 15 octombrie 2014 10:58:27
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define DN 120005
#define pb push_back
#define bp pop_back
#define sz size
#define x first
#define y second
using namespace std;

typedef pair<double,double> per;

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

int id(per a,per b,per c) {
  double s=b.x*c.y+c.x*a.y+a.x*b.y;
  double d=a.x*c.y+c.x*b.y+b.x*a.y;
  return s-d<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);
  st.pb(p[0]); st.pb(p[1]);
  for(int i=2; i<n; ++i) {
    for(;st.sz() && id(st[st.sz()-2],st.back(),p[i]);st.bp());
    st.pb(p[i]);
  }
  st.bp();
  for(int i=n-1; i>=0; --i) {
    for(;st.sz() && id(st[st.sz()-2],st.back(),p[i]);st.bp());
    st.pb(p[i]);
  }
  st.bp();
  g<<st.sz()<<'\n';
  for(int i=0; i<st.sz(); ++i) g<<fixed<<setprecision(8)<<st[i].x<<' '<<st[i].y<<'\n';
}