Cod sursa(job #1589879)

Utilizator robertstrecheStreche Robert robertstreche Data 4 februarie 2016 15:38:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 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],s[lmax];

double unghi(el a,el b,el c)
{
    return a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-a.y*b.x-a.x*c.y;
}

int comp(el e1,el e2)
{
    return unghi(v[1],e1,e2)>0;
}

int n,nr,i,a,b,c;

int main()
{
    f>>n>>v[1].x>>v[1].y;

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

         if (v[i].x!=v[1].x)
          {
              if (v[i].x<v[1].x)
               swap(v[1],v[i]);
          }
         else
          if (v[i].y<v[1].y)
           swap(v[1],v[i]);

     }

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

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

    nr=2;

    for (i=3;i<=n;i++)
     {

         while (unghi(s[nr-1],s[nr],v[i])<=0 && nr>=2)
              nr--;

         nr++;
         s[nr]=v[i];

     }

    g<<nr<<'\n';

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

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