Cod sursa(job #1193785)

Utilizator robertstrecheStreche Robert robertstreche Data 1 iunie 2014 19:22:14
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 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];

int comp(el e1,el e2)
{
    int m1=0,m2=0;

    if (v[1].x-e1.x)
     m1=(v[1].y-e1.y)/(v[1].x-e1.x);

    if (v[1].x-e2.x)
     m2=(v[1].y-e2.y)/(v[1].x-e2.x);

    return m1<m2;
}

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].y<v[1].y)
               swap(v[1],v[i]);
          }
         else
          if (v[i].x<v[1].x)
           swap(v[1],v[i]);

     }

    sort(v+2,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;

    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)
          {
              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();
}