Cod sursa(job #3246562)

Utilizator David_PoterasuDavid Poterasu David_Poterasu Data 3 octombrie 2024 17:14:30
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.06 kb
#include <fstream>
#include <stack>
#include <iomanip>
#include <algorithm>

using namespace std;

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

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

int s[MAX], ns, s2[MAX], ns2;

bool verif_jos(int i, int xa, int ya, int xb, int yb)
{
  int xc=v[i].x, yc=v[i].y;
  if((xa*yb+xb*yc+xc*ya)<(ya*xb+yb*xc+yc*xa))
  {
    return 1;
  }
  return 0;
}

bool cmp(ura a, ura b)
{
  if(a.x>b.x)
    return 0;
  else if(a.x<b.x)
    return 1;
  if(a.y<b.y)
    return 1;
  return 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);






    float xa=v[1].x, ya=v[1].y, xb=v[n].x, yb=v[n].y;
    ns+=2;
    s[1]=1;
    s[2]=n;
    for(int i=2; i<n; i++)
    {
      if(verif_jos(i, xa, ya, xb, yb))
      {
        if(verif_jos(i, v[s[ns-1]].x, v[s[ns-1]].y, v[s[ns]].x, v[s[ns]].y))
        {
          while(ns>1 && verif_jos(i, v[s[ns-1]].x, v[s[ns-1]].y, v[s[ns]].x, v[s[ns]].y))
          {
            ns--;
          }
          ns++;
          s[ns]=i;
        }
        else
        {
          ns++;
          s[ns]=i;
        }
      }
    }


    ns2+=2;
    s2[1]=n;
    s2[2]=1;
    for(int i=n-1; i>=1; i--)
    {
      if(!verif_jos(i, xa, ya, xb, yb))
      {
        if(!verif_jos(i, v[s2[ns2]].x, v[s2[ns2]].y, v[s2[ns2-1]].x, v[s2[ns2-1]].y))
        {
          while(ns2>1 && verif_jos(i, v[s2[ns2]].x, v[s2[ns2]].y, v[s2[ns2-1]].x, v[s2[ns2-1]].y))
          {
            ns2--;
          }
          ns2++;
          s2[ns2]=i;
        }
        else
        {
          ns2++;
          s2[ns2]=i;
        }
      }
    }




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