Cod sursa(job #2659678)

Utilizator ScortiaClaudiaScortia Claudia ScortiaClaudia Data 17 octombrie 2020 12:00:59
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

struct punct{
    double x,y;
} ;

punct v1[120001],v2[120001];

void citire(int &n,punct a[120001])
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i].x;
        fin>>a[i].y;
    }
}

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

/*void ordonare(int n,punct a[120001])
{
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
    {
        if(a[i].x > a[j].x)
            swap(a[i],a[j]);
        else if(a[i].x == a[j].x && a[i].y > a[j].y)
            swap(a[i],a[j]);
    }
}*/
bool cnd(punct a,punct b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
};

void ordonare(int n,punct a[120001])
{
    sort(a,a+n,cnd);
}

void formarev1(punct a[120001],int n,int &last)
{
    v1[1]=a[1];
    v1[2]=a[2];
    last=2;
    for(int i=3;i<=n;i++)
    {
        if(determinant(v1[last-1],v1[last],a[i])<0)
            {
                last--;
                while(last!=1 && determinant(v1[last-1],v1[last],a[i])<0)
                    last--;
                v1[++last]=a[i];
            }
        else if(determinant(v1[last-1],v1[last],a[i])>=0)
        {
            v1[++last]=a[i];
        }
    }
}

void formarev2(punct a[120001],int n,int &last)
{
    v2[1]=a[n];
    v2[2]=a[n-1];
    last=2;
    for(int i=n-2;i>=1;i--)
    {
        if(determinant(v2[last-1],v2[last],a[i])<0)
            {
                last--;
                while(last!=1 && determinant(v2[last-1],v2[last],a[i])<0)
                    last--;
                v2[++last]=a[i];
            }
        else if(determinant(v2[last-1],v2[last],a[i])>=0)
        {
            v2[++last]=a[i];
        }
    }
}

void afisare(int x,int y)
{
    int i;
    fout<<x+y-2<<"\n";
    for(i=1;i<=x;i++)
        fout<<fixed<<setprecision(6)<<v1[i].x<<" "<<v1[i].y<<"\n";
    for(i=2;i<y;i++)
        fout<<fixed<<setprecision(6)<<v2[i].x<<" "<<v2[i].y<<"\n";
}

int main()
{
    int n,x,y;
    punct a[120001];
    citire(n,a);
    ordonare(n,a);
    formarev1(a,n,x);
    formarev2(a,n,y);
    afisare(x,y);
    return 0;
}