Cod sursa(job #3247500)

Utilizator Theo_Ivanescu Teodora Theo_ Data 8 octombrie 2024 08:58:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

const int MAX=120005;
struct ura
{   double x, y;
}   v[MAX];

int s[MAX], vf;

bool cmp(ura a, ura b)
{
  if(a.x==b.x)
    return a.y<b.y;
  return a.x<b.x;
}
bool verif_jos(int a, int b, int c)
{
  double ax=v[a].x;
  double ay=v[a].y;
  double bx=v[b].x;
   double by=v[b].y;
   double cx=v[c].x;
   double cy=v[c].y;
  return (ax*by+bx*cy+cx*ay-ay*bx-by*cx-cy*ax)<0;
}

int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
      cin>>v[i].x>>v[i].y;
    }
    sort(v+1, v+n+1, cmp);
    s[++vf]=1;
    for(int i=2; i<=n; i++)
    {
      if(verif_jos(1, n, i) || i==n)
      {
        while(vf>1 && verif_jos(s[vf-1], s[vf], i))
        {
          vf--;
        }
        s[++vf]=i;
      }
    }
    int vf1=vf;
    for(int i=n-1; i>=1; i--)
    {
      if(!verif_jos(1, n, i) || i==1)
      {
        while(vf>vf1 && verif_jos(s[vf-1], s[vf], i))
        {
          vf--;
        }
        s[++vf]=i;
      }
    }
    cout<<vf-1<<endl;
    cout<<fixed<<setprecision(6);
    for(int i=2; i<=vf; i++)
    {
      cout<<v[s[i]].x<<" "<<v[s[i]].y<<endl;
    }
    return 0;
}