Cod sursa(job #3195709)

Utilizator biancaivascuBianca Ivascu biancaivascu Data 21 ianuarie 2024 15:37:59
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;
#define MaxN 120000
struct st
{
  double x,y;
};
st v[MaxN];
vector <st> stiva;
int points;
int findpoint(int n)
{
  int pos, i;
  pos=0;
  for(i=0; i<n; i++)
  {
    if(v[i].y < v[pos].y || (v[i].y==v[pos].y && v[i].x < v[pos].x))
      pos=i;
  }
  return pos;
}
double orientation(const st& a, const st& b, const st& c)
{
  return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}
int cmp(const st& a, const st& b)
{
  return orientation(v[0], a, b)<0;
}

void inf_convexa(int n)
{
  int i;
  stiva.push_back(v[0]);
  stiva.push_back(v[1]);
  for(i=2; i<n; i++)
  {
    while(stiva.size()>=2 && orientation(stiva[stiva.size()-2], stiva.back(), v[i])>=0)
    {
      stiva.pop_back();
    }
    stiva.push_back(v[i]);
  }
}

int main()
{
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");
    int n, i;
    in>>n;
    for(i=0; i<n; i++)
    {
      in>>v[i].x>>v[i].y;
    }
    swap(v[0], v[findpoint(n)]);
    sort(v+1, v+n, cmp);
    inf_convexa(n);
    out<<stiva.size()<<'\n';
    out<<setprecision(12)<<fixed;
    for(const st& p: stiva)
    {
      out<<p.x<<" "<<p.y<<'\n';
    }
    return 0;
}