Cod sursa(job #2857741)

Utilizator alextheseal1240Alex Vladu alextheseal1240 Data 26 februarie 2022 11:20:41
Problema Infasuratoare convexa Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#define inf 0x3f3f3f3f
#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, deg;
}v[120100], origin;
vector<punct>s;
vector<punct>rez;
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 1.0*(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)
{
    long double d=1.0*(origin.x-a.x)*(origin.x-a.x)+(origin.y-a.y)*(origin.y-a.y);
    if(d==0)
        return 0.0;
    return acos(1.0*(a.x-origin.x)/sqrt(d));
}
int main()
{
    read();
    origin.x=inf, origin.y=inf;
    for(int i=1; i<=n; i++)
    {
        if(origin.y>v[i].y)
            origin=v[i];
        if(origin.y==v[i].y && origin.x>v[i].x)
            origin=v[i];
    }
    for(int i=1; i<=n; i++)
        v[i].deg=angle(v[i]);
    sort(v+1, v+n+1, [](punct a, punct b){return a.deg<b.deg;});
    s.push_back(v[1]), s.push_back(v[2]), s.push_back(v[3]);
    int ind=4;
    while(1)
    {
        punct c=s.back();
        s.pop_back();
        punct b=s.back();
        s.pop_back();
        punct a=s.back();
        s.pop_back();
        if(valid(a, b, c) && ind<=n)
        {
            s.push_back(a), s.push_back(b), s.push_back(c), s.push_back(v[ind++]);
            continue;
        }
        if(s.size()==0 && ind<=n)
        {
            s.push_back(a), s.push_back(c), s.push_back(v[ind++]);
            continue;
        }
        s.push_back(a), s.push_back(c);
        if(ind==n+1)
            break;
    }
    fout << s.size() << '\n';
    for(auto x:s)
        fout << fixed << setprecision(6) << x.x << ' ' << x.y << '\n';
    return 0;
}