Cod sursa(job #2208813)

Utilizator ElektrykT E S L A P E F E L I E Elektryk Data 31 mai 2018 18:51:11
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

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

struct puncte
{
    double x, y;
    /// dreapta=1 si stanga=2
    int position;
}v[100001];

inline bool sortingParameter(puncte a, puncte b)
{
    return a.y<b.y || ( a.y==b.y && a.x<b.x );
}

double checkWay(int p, int p1, int p2)
{
    return v[p1].x*v[p2].y + v[p2].x*v[p].y + v[p].x*v[p1].y - v[p].x*v[p2].y - v[p1].x*v[p].y -v[p2].x*v[p1].y;
}

int n, stack1[100001], stack2[100001];

int main()
{
    in>>n;
    for(register int i=1; i<=n; ++i)
        in>>v[i].x>>v[i].y;
    sort(v+1, v+n+1, sortingParameter);
    for(register int i=2; i<n; ++i)
        if(checkWay(i, 1, n)<0)
            v[i].position=1;
        else
            v[i].position=2;
    int k=0;
    stack1[++k]=1;
    for(register int i=2; i<n; ++i)
    {
        if(k>=2 && v[i].position==1 && checkWay(i, stack1[k-1], stack1[k])>0)
            stack1[++k]=i;
        else if(k>=2 && v[i].position==1 && checkWay(i, stack1[k-1], stack1[k])<0)
            stack1[k]=i;
        else if(v[i].position==1 && k==1)
            stack1[++k]=i;
    }
    stack1[++k]=n;
    int k2=0;
    stack2[++k2]=1;
    for(register int i=2; i<n; ++i)
    {
        if(k>=2 && v[i].position==2 && checkWay(i, stack2[k2-1], stack2[k2])<0)
            stack2[++k2]=i;
        else if(k>=2 && v[i].position==2 && checkWay(i, stack2[k2-1], stack2[k2])>0)
            stack2[k2]=i;
        else if(v[i].position==2 && k==1)
            stack2[++k2]=i;
    }
    out<<fixed;
    for(register int i=1; i<=k; ++i)
        out<<setprecision(6)<<v[stack1[i]].x<<" "<<setprecision(6)<<v[stack1[i]].y<<'\n';
    for(register int i=k2; i>=1; --i)
        out<<setprecision(6)<<v[stack2[i]].x<<" "<<setprecision(6)<<v[stack2[i]].y<<'\n';
    return 0;
}