Cod sursa(job #3348659)

Utilizator Victor5539Tanase Victor Victor5539 Data 23 martie 2026 12:38:42
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#pragma GCC target("avx,avx2,fma")
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");


const int NMAX=12e4;
int n,i;
stack <int> s;
vector <int> sol;

struct point{
double x,y;}v[NMAX+5];

bool compare1(point a , point b)
{
    if (a.y!=b.y)
        return a.y<b.y;

    return a.x<b.x;
}

double det(point a, point b, point 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;
}

double dist(point a, point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

bool compare2(point a, point b)
{
    double angle=det(v[1],a,b);

    if (angle==0)
        return dist(v[1],a)<dist(v[1],b);

    return angle>0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr); fout.tie(nullptr);

    fin>>n;
    for (i=1; i<=n; i++)
        fin>>v[i].x>>v[i].y;

    sort(v+1,v+n+1,compare1);
    sort(v+2,v+n+1,compare2);

    s.push(1);
    s.push(2);

    for (i=3; i<=n; i++)
    {
        while (s.size()>=2)
        {
            int idx1=s.top();
            s.pop();
            int idx2=s.top();

            if (det(v[idx2],v[idx1],v[i])>0)
            {
                s.push(idx1);
                break;
            }
        }

        s.push(i);
    }


    while (!s.empty())
    {
        sol.push_back(s.top());
        s.pop();
    }

    reverse(sol.begin(),sol.end());
    fout<<sol.size()<<'\n';

    for (auto x: sol)
        fout<<fixed<<setprecision(12)<<v[x].x<<" "<<v[x].y<<'\n';


    return 0;
}