Cod sursa(job #1620957)

Utilizator StrokeSimion Valentin Stroke Data 29 februarie 2016 14:38:27
Problema Infasuratoare convexa Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define eps 1e-12
#define max_n 120050

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

struct punct {double x,y;};
punct p[max_n+1],v[max_n+1];
int i,h,n,s[max_n+1],ok[max_n+1];

inline int cmp1 (double a,double b)
{ if(a+eps<b)
   return 1;
   if(b+eps<a)
    return -1;
    return 0;

}

bool cmp (const punct &a, const punct &b)
 { int t;
   t=cmp1(a.x,b.x);
   if(t!=0)
     return t==1;
     return (cmp1(a.y,b.y)==1);

 }

 int semn (punct a, punct b, punct c)
  {
      return cmp1(a.x*b.y+c.x*a.y+b.x*c.y-c.x*b.y-c.y*a.x-a.y*b.x,0);
  }
void rezolva()
{
    int k,q;
    sort(v+1,v+n,cmp);
    s[1]=1;
    s[2]=2;
    ok[2]=1;
    k=2;
    i=3;
    q=1;
    while(1)
    {
        while(ok[i])
        {
            if(i==n)
            q=-1;
            i=i+q;

        }
        while(k>=2&&semn(v[s[k-1]],v[s[k]],v[i])==-1)
        {
            ok[s[k]]=0;
            k--;
        }
        s[++k]=i;
        ok[i]=1;
    if(ok[1]==1)
        break;
    }
    h=k-1;
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>v[i].x>>v[i].y;

    rezolva();
    g<<h<<'\n';
    g<<setprecision(6)<<fixed;
    for(i=h;i>=1;--i)
    g<<v[s[i]].x<<' '<<v[s[i]].y<<'\n';
    return 0;
}