Cod sursa(job #2134375)

Utilizator netfreeAndrei Muntean netfree Data 17 februarie 2018 21:28:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#define x first
#define y second
#define ld double
#define pii pair<double, double>
#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX = 120000 + 5;

int n, stsz;
pii pct[N_MAX];
pii st[N_MAX];

ld deter(pii a, pii b, pii c){
  return ((a.x - c.x)*(b.y - c.y) + (b.x - c.x)*(c.y - a.y));
}

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

  sort(pct + 1, pct + n + 1);

  for(int i = 1; i<=n; ++i){
    while(stsz >= 2 and deter(st[stsz-1], st[stsz], pct[i]) > 0)
      stsz --;
    st[++stsz] = pct[i];
  }

  for(int i = n-1; i>=1; --i){
    while(stsz >= 2 and deter(st[stsz-1], st[stsz], pct[i]) > 0)
      stsz --;
    st[++stsz] = pct[i];
  }

  stsz--;

  fout << stsz << '\n';
  for(int i = stsz; i>=1; --i)
    fout << fixed << setprecision(12) << st[i].x << " " << st[i].y << '\n';

  return 0;
}

//Andrei Muntean, 2018