Cod sursa(job #1193780)

Utilizator robertstrecheStreche Robert robertstreche Data 1 iunie 2014 18:55:12
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

#define lmax 120005

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct el
{
   long double x,y;
}
v[lmax];

struct ell
{
   long double x,y;
   int ind;
}
s[lmax];

int comp(el e1,el e2)
{
    if (e1.y!=e2.y)
     return e1.y<e2.y;

    return e1.x<e2.x;
}

int n,nr,i,a,b,c;
bool ap[lmax];

int main()
{
    f>>n;

    for (i=1;i<=n;i++)
     f>>v[i].x>>v[i].y;

    sort(v+1,v+n+1,comp);


    s[1].x=v[1].x;
    s[2].x=v[2].x;

    s[1].y=v[1].y;
    s[2].y=v[2].y;

    s[1].ind=1;
    s[2].ind=2;

    nr=2;

    for (i=3;i<=n;i++)
     {
         a=s[nr-1].y-s[nr].y;
         b=s[nr].x-s[nr-1].x;
         c=s[nr-1].x*s[nr].y-s[nr].x*s[nr-1].y;

          while (a*v[i].x+b*v[i].y+c<0)
           {

               ap[s[nr].ind]=0;
               nr--;

               a=s[nr-1].y-s[nr].y;
               b=s[nr].x-s[nr-1].x;
               c=s[nr-1].x*s[nr].y-s[nr].x*s[nr-1].y;
           }

               nr++;
               ap[i]=1;
               s[nr].y=v[i].y;
               s[nr].x=v[i].x;
               s[nr].ind=i;
     }

     for (i=n;i>=3;i--)
      if (!ap[i])
      {
         a=s[nr-1].y-s[nr].y;
         b=s[nr].x-s[nr-1].x;
         c=s[nr-1].x*s[nr].y-s[nr].x*s[nr-1].y;

          while (a*v[i].x+b*v[i].y+c<0)
           {
               nr--;

               a=s[nr-1].y-s[nr].y;
               b=s[nr].x-s[nr-1].x;
               c=s[nr-1].x*s[nr].y-s[nr].x*s[nr-1].y;
           }

               nr++;
               s[nr].y=v[i].y;
               s[nr].x=v[i].x;
     }


     g<<nr<<'\n';

     for (i=1;i<=nr;i++)
      g<<fixed<<setprecision(6)<<s[i].x<<" "<<s[i].y<<'\n';

    f.close();
    g.close();
}