Cod sursa(job #2432489)

Utilizator MortemPlaiasu Iulia-Silvia Mortem Data 23 iunie 2019 22:24:55
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

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

typedef std::pair<double, double> Point;
#define x first
#define y second 
const double ERR = 1e-12;

struct Comp: std::binary_function<Point,Point,bool>
{
  bool operator() (Point p1, Point p2)
  {
    if(p1.y != p2.y)
      return p1.y<p2.y;
    return p1.x<p2.x;
  }  
};

int n;
std::vector<std::pair<double, double> >v;
int head;
int stack[120005];
bool vis[120005];
double cross_product(Point O, Point A, Point B)
{
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}

int main()
{
  fin>>n;
  std::cout<< std::setprecision(6) << std::fixed;
  fout<< std::setprecision(6) << std::fixed;
  for(int i=0;i<n;i++)
  {
    double x,y;
    fin>>x>>y;
    v.push_back(std::make_pair(x,y));
  }
  std::sort(v.begin(), v.begin()+n,Comp());
  stack[0]=0;
  stack[1]=1;
  vis[1]=true;
 // vis[0]=true;
  head=2;
  int p=1;
  for(int i=1;i>=0;i+=(p= (i==n-1)?-p:p))
  {
    if (vis[i]) continue;
    while(head>=2 && cross_product(v[stack[head-2]],v[stack[head-1]],v[i])<ERR)
    {
      vis[stack[head-1]]=false;
      head--;
    }
    vis[i]=true;
    stack[head]=i;
    head++;
  }
  fout<<head-1<<"\n";
  for(int i=0;i<head-1;i++)
    fout<<v[stack[i]].x<<" "<<v[stack[i]].y<<"\n";
}