Cod sursa(job #3246713)

Utilizator David_PoterasuDavid Poterasu David_Poterasu Data 4 octombrie 2024 10:00:23
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("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, ay=v[a].y, bx=v[b].x, by=v[b].y, cx=v[c].x, cy=v[c].y;
  return (ax*by+bx*cy+cx*ay-ay*bx-by*cx-cy*ax)<0;
}

int main()
{
    int n;
    fin>>n;
    for(int i=1; i<=n; i++)
    {
      fin>>v[i].x>>v[i].y;
    }
    sort(v+1, v+n+1, cmp);


    vf+=2;
    s[1]=1;
    s[2]=n;
    for(int i=2; i<n; i++)
    {
      if(verif_jos(1, n, i))
      {
        while(vf>1 && verif_jos(s[vf-1], s[vf], i))
        {
          vf--;
        }
        s[++vf]=i;
      }
    }
    int vf1=vf;

    s[++vf]=n;
    for(int i=n-1; i>1; i--)
    {
      if(!verif_jos(1, n, i))
      {
        while(vf>vf1 && verif_jos(s[vf-1], s[vf], i))
        {
          vf--;
        }
        s[++vf]=i;
      }
    }

    fout<<vf<<'\n';
    fout<<fixed<<setprecision(6);
    for(int i=2; i<=vf; i++)
    {
      fout<<v[s[i]].x<<" "<<v[s[i]].y<<'\n';
    }
    fout<<v[s[1]].x<<" "<<v[s[1]].y<<'\n';
    return 0;
}