Cod sursa(job #3195727)

Utilizator Sara_BalanoiuSara Balanoiu Sara_Balanoiu Data 21 ianuarie 2024 15:58:30
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

int n;
struct punct
{
  double x, y;
} p[120000];
vector<punct> st;

int pstart()
{
  int i1=0;
  for(int i=1; i<n; i++)
  {
    if(p[i].y<p[i1].y || (p[i].y==p[i1].y && p[i].x<p[i1].x))
      i1=i;
  }
  return i1;
}
double orientare(const punct& a, const punct& b, const punct& c)
{
  return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}
bool cmp(const punct& a, const punct& b)
{
  return orientare(p[0], a, b)<0;
}
void cst()
{
  st.push_back(p[0]);
  st.push_back(p[1]);
  for(int i=2; i<n; i++)
  {
    while(st.size()>=2 && orientare(st[st.size()-2], st.back(), p[i])>=0)
      st.pop_back();
    st.push_back(p[i]);
  }
}

int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    cin>>n;
    for(int i=0; i<n; i++)
      cin>>p[i].x>>p[i].y;
    swap(p[0], p[pstart()]);
    sort(p+1, p+n, cmp);
    cst();
    cout<<st.size()<<'\n';
    cout << setprecision(6) << fixed;
    for(const punct& q : st)
      cout<<q.x<<' '<<q.y<<'\n';
    return 0;
}