Cod sursa(job #2220059)

Utilizator roberttrutaTruta Robert roberttruta Data 10 iulie 2018 14:18:04
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
int n,afis[120002],t,i;
struct vct
{
    double x,y;
}v[120002];
bool cmp (vct A , vct B)
{
    if (A.y==B.y)
        return A.x<B.x;
    else
        return A.y<B.y;
}
int determinant(int x, int y, int z)
{
    double delta,a1,a2,a3,b1,b2,b3;
    a1=v[x].x; b1=v[x].y;
    a2=v[y].x; b2=v[y].y;
    a3=v[z].x; b3=v[z].y;
    delta=a1*b2+a2*b3+a3*b1-a3*b2-a1*b3-a2*b1;
    if(delta>=0)
        return 1;
    else
        return 0;
}
int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");

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

    sort(v+1,v+1+n,cmp);
    afis[1]=1;
    afis[2]=2;
    t=2;
    for(i=3;i<=n;i++)
    {
        if(!determinant(afis[t],afis[t-1],i))
            afis[++t]=i;
        else
        {
            while(determinant(afis[t],afis[t-1],i))
            t--;
            afis[++t]=i;
        }
    }
    afis[++t]=n-1;
    for(i=n-2;i>=1;i--)
    {
        if(!determinant(afis[t],afis[t-1],i))
            afis[++t]=i;
        else
        {
            while(determinant(afis[t],afis[t-1],i))
            t--;
            afis[++t]=i;
        }
    }
    g<<t-1<<'\n';
    for(i=1;i<t;i++)
        g<<fixed<<setprecision(6)<<v[afis[i]].x<<' '<<fixed<<setprecision(6)<<v[afis[i]].y<<'\n';




    return 0;
}