Cod sursa(job #1756029)

Utilizator medicinedoctoralexandru medicinedoctor Data 11 septembrie 2016 17:29:35
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>

using namespace std;

struct point {
       double x,y,a;
} minp,a[120000],h[120000];

int n,m;
ifstream fin("infasuratoare.in");
ofstream out("infasuratoare.out");

void sw(point *x,point *y)
{
     point q=*x;
     *x=*y;
     *y=q;
}

void qs(int le,int ri)
{
     int i=le,j=ri; point p=a[(i+j)/2];
     while (i<j)
     {
           while (a[i].a<p.a) i++;
           while (a[j].a>p.a) j--;
           if (i<=j)
           {
                    sw(&a[i],&a[j]);
                    i++;
                    j--;
           }
     }
     if (i<ri) qs(i,ri);
     if (le<j) qs(le,j);
}

double ab(double x)
{
       if (x<0) return x*-1; else return x;
}

void ca()
{
     for (int i=1; i<=n; i++)
     {
         double c1=a[i].y-minp.y,c2=a[i].x-minp.x;
         if ((c1==0) & (c2==0)) a[i].a=1.1;
         else a[i].a=c1*ab(c1)/(c1*c1+c2*c2);
     }
     qs(1,n);
}

void lire()
{
     fin >> n >> a[1].x >> a[1].y;
     minp=a[1];
     for (int i=2; i<=n; i++)
     {
         fin >> a[i].x >> a[i].y;
         if ((minp.x>a[i].x) | (minp.x==a[i].x) & (minp.y<a[i].y))
         minp=a[i];
     }
     ca();
}

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

void hull()
{
     m=3;
     for (int i=1; i<=3; i++)
         h[i]=a[i];
     for (int i=4; i<=n; i++)
     {
         m++;
         h[m]=a[i];
         while ((m>2) & (det(h[m-2],h[m-1],h[m]) <=0))
         {
               h[m-1]=h[m];
               m--;
         }
     }
     out << m << endl;
     for (int i=1; i<=m; i++)
         out << h[i].x << " " << h[i].y << endl;
}

int main()
{
    lire();
    hull();
    return 0;
}