Cod sursa(job #3246966)

Utilizator tudorhTudor Horobeanu tudorh Data 4 octombrie 2024 21:57:26
Problema Infasuratoare convexa Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct
{
    double x,y;
    bool t;
}pct[120001];
vector <Punct> s;
bool sortpct(Punct a,Punct b)
{
    return(a.x<b.x || (a.x==b.x && a.y<b.y));
}

double Arie(Punct a,Punct b,Punct c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y;
}
int main()
{
    int n;
    double x,y;
    fin>>n;
    for(int i=0;i<n;i++)
    {
        fin>>x>>y;
        pct[i]={x,y};
    }
    sort(pct,pct+n,sortpct);
    for(int i=1;i<n-1;i++)
    {
        double arie=Arie(pct[0],pct[n-1],pct[i]);
        pct[i].t=(arie>0);
    }
    for(int i=0;i<n-1;i++)
    {
        if(pct[i].t)
            continue;
        while(s.size()>=2)
        {
            double arie=Arie(s[s.size()-2],s[s.size()-1],pct[i]);
            if(arie<0)
                s.pop_back();
            else break;
        }

        s.push_back(pct[i]);
    }
    int size0=s.size();
    pct[n-1].t=pct[0].t=1;
    for(int i=n-1;i>=0;i--)
    {
        if(!pct[i].t)
            continue;
        while(s.size()-size0>=2)
        {
            double arie=Arie(s[s.size()-2],s[s.size()-1],pct[i]);
            if(arie<0)
                s.pop_back();
            else break;
        }
        s.push_back(pct[i]);

    }
    s.pop_back();
    fout<<s.size()<<'\n'<<fixed<<setprecision(6);
    for(int i=0;i<s.size();i++)
        fout<<s[i].x<<" "<<s[i].y<<'\n';
    return 0;
}