Cod sursa(job #1829850)

Utilizator DavidDragulinDragulin David DavidDragulin Data 15 decembrie 2016 18:59:34
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int ind;
double det;
int i,j,k,n,prez[120002];
struct punct
{
    int ind;
    double x,y;
}a[120002],v[120002];
int compare(punct x,punct y)
{
    if(x.y!=y.y)
        return x.y<y.y;
    return x.x<y.x;
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i].x>>a[i].y,a[i].ind=i;
    sort(a+1,a+n+1,compare);
    for(i=1;i<=n;i++)
        a[i].ind=i;
    v[1]=a[1];
    v[2]=a[2];
    prez[1]=1;
    prez[2]=1;
    i=2;
    k=2;
   while(i<n)
   {
        i++;
        det=v[k-1].x *v[k].y  + v[k].x *a[i].y + a[i].x * v[k-1].y - a[i].x * v[k].y - v[k-1].x * a[i].y - v[k].x * v[k-1].y;
        while(det>0&&k>2)
        {
            prez[v[k].ind]=0;
            k--;
        det=v[k-1].x *v[k].y  + v[k].x *a[i].y + a[i].x * v[k-1].y - a[i].x * v[k].y - v[k-1].x * a[i].y - v[k].x * v[k-1].y;

        }
        k++;
        v[k]=a[i];
        prez[v[k].ind]=1;
    }
       while(i>1)
   {
        i--;
        if(prez[a[i].ind]==1)
            continue;
        det=v[k-1].x *v[k].y  + v[k].x *a[i].y + a[i].x * v[k-1].y - a[i].x * v[k].y - v[k-1].x * a[i].y - v[k].x * v[k-1].y;

        while(det>0)
        {
            prez[v[k].ind]=0;
            k--;
        det=v[k-1].x *v[k].y  + v[k].x *a[i].y + a[i].x * v[k-1].y - a[i].x * v[k].y - v[k-1].x * a[i].y - v[k].x * v[k-1].y;

        }
        k++;
        v[k]=a[i];
        prez[v[k].ind]=1;
    }
    fout<<k<<'\n';
    fout<<fixed<<setprecision(12)<<v[1].x<<" "<<v[1].y<<'\n';
    for(i=k;i>=2;i--)
        fout<<fixed<<setprecision(12)<<v[i].x<<" "<<v[i].y<<'\n';
    return 0;
}