Cod sursa(job #2857422)

Utilizator alextheseal1240Alex Vladu alextheseal1240 Data 25 februarie 2022 16:18:22
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>
#include <stack>
#include <queue>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct punct{
    long double x, y;
}v[120001];
stack<punct>s;
vector<punct>rez;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
void read()
{
    fin >> n;
    for(int i=1; i<=n; i++)
        fin >> v[i].x >> v[i].y;
}
bool valid(punct a, punct b, punct c)
{
    return (a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-b.x*a.y-a.x*c.y)>=0;
}
long double angle(punct a)
{
    return (v[1].y-a.y)/(v[1].x-v[1].y);
}
int main()
{
    read();
    sort(v+1, v+n+1, [](punct a, punct b){return a.y==b.y?a.x<b.x:a.y<b.y;});
    sort(v+2, v+n+1, [](punct a, punct b){return angle(a)<angle(b);});
    s.push(v[1]), s.push(v[2]), s.push(v[3]);
    int ind=4;
    while(ind<=n)
    {
        punct c=s.top();
        s.pop();
        punct b=s.top();
        s.pop();
        punct a=s.top();
        s.pop();
        if(valid(a, b, c))
        {
            s.push(a), s.push(b), s.push(c), s.push(v[ind++]);
            if(ind==n+1)
                break;
        }
        else if(s.size()==0)
            s.push(a), s.push(c), s.push(v[ind++]);
        else
            s.push(a), s.push(c);
    }
    fout << s.size() << '\n';
    while(!s.empty())
        rez.push_back({s.top().x, s.top().y}), s.pop();
    for(auto it=rez.rbegin(); it!=rez.rend(); it=it+1)
        fout << fixed << setprecision(6) << it->x << ' ' << it->y << '\n';
    return 0;
}