Cod sursa(job #2899889)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 9 mai 2022 16:04:57
Problema Infasuratoare convexa Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
/// always:
#include <cstdio>
#include <string>

/// optional:
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>

bool home = 1;
using namespace std;

typedef long double ld;
const string TASKNAME="infasuratoare";

const int N=120000+7;

int n;

struct Vec{
  ld x;
  ld y;
};

ld f(Vec a,Vec b) {
  return (a.x-b.x)*(a.y+b.y);
}

ld f(Vec a,Vec b, Vec c) {
  return f(a,b)+f(b,c)+f(c,a);
}

Vec v[N];

bool cmp(Vec x,Vec y) {
  return f(v[1],x,y)>0;
}

bool sm(Vec a,Vec b) {
  if(a.y!=b.y) return a.y<b.y;
  return a.x<b.x;
}

signed main() {
#ifdef INFOARENA
  home = 0;
#endif
  ///home=0;
  if(!home) {
    freopen((TASKNAME + ".in").c_str(), "r", stdin);
    freopen((TASKNAME + ".out").c_str(), "w", stdout);
  }else{
    freopen ("I_am_iron_man", "r", stdin);
  }

  cin>>n;
  for (int i=1;i<=n;i++) {
    cin>>v[i].x>>v[i].y;
    if(sm(v[i],v[1])) swap(v[i],v[1]);
  }

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

  v[n+1]=v[1];

  vector<Vec> stk;
  for (int i=1;i<=n+1;i++) {
    while((int)stk.size()>=2&&f(stk[(int)stk.size()-2],stk[(int)stk.size()-1],v[i])<0) {
      stk.pop_back();
    }
    stk.push_back(v[i]);
  }
  stk.pop_back();
  cout<<(int)stk.size()<<"\n";
  for (auto &p:stk){
    cout<<fixed<<setprecision(6)<<p.x<<" "<<p.y<<"\n";
  }

}