Cod sursa(job #3032249)

Utilizator tudor_costinCostin Tudor tudor_costin Data 21 martie 2023 19:59:08
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int Nmax=120005;
int mlx,mly;
struct Point{
    double x,y;
};
bool cmp (Point p,Point b)
{
    return (p.x-mlx)*(b.y-mly)>(b.x-mlx)*(p.y-mly);
}
Point a[Nmax];
bool isInside(int i,int j,int k)
{
     return (a[k].x-a[i].x)*(a[j].y-a[i].y)>(a[j].x-a[i].x)*(a[k].y-a[i].y);
}
stack<int> s;
int main()
{
    int n;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i].x>>a[i].y;
    }
    int mostleft=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i].x<a[mostleft].x)
        {
            mostleft=i;
        }
        if(a[i].x==a[mostleft].x)
        {
            if(a[i].y<a[mostleft].y)
            {
                mostleft=i;
            }
        }
    }
    Point aux=a[mostleft];
    a[mostleft]=a[1];
    a[1]=aux;
    mlx=a[1].x;
    mly=a[1].y;
    sort(a+2,a+n+1,cmp);
    s.push(1);
    s.push(2);
    for(int i=2;i<=n;i++)
    {
        int t=s.top();
        s.pop();
        int t2=s.top();
        s.push(t);
        while(isInside(i,s.top(),t2) && s.size()>=2)
        {
            s.pop();
            t=s.top();
            s.pop();
            t2=s.top();
            s.push(t);
        }
        s.push(i);
    }
    while(!s.empty())
    {
        fout<<setprecision(9)<<a[s.top()].x<<' '<<a[s.top()].y<<'\n';
        s.pop();
    }
    return 0;
}