Cod sursa(job #3358750)

Utilizator TianaInfoLitcanu Tiana TianaInfo Data 19 iunie 2026 21:47:19
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
using namespace std;

struct pct
{
    long double x,y;
};
bool cmp(pct a,pct b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
pct p[120001];
vector<pct> h;

long double sens(pct a,pct b,pct c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define cin fin
#define cout fout
int n;
int main()
{
    cin>>n;

    for(int i=0;i<n;i++)
        cin>>p[i].x>>p[i].y;

    sort(p,p+n,cmp);

    for(int i=0;i<n;i++)
    {
        while(h.size()>=2 && sens(h[h.size()-2],h[h.size()-1],p[i])<=0)
            h.pop_back();

        h.push_back(p[i]);
    }

    int k=h.size();

    for(int i=n-2;i>=0;i--)
    {
        while(h.size()>k && sens(h[h.size()-2],h[h.size()-1],p[i])<=0)
            h.pop_back();

        h.push_back(p[i]);
    }
    h.pop_back();


    cout<<h.size()<<'\n';
    cout<<fixed<<setprecision(6);
    for(int i=0;i<h.size();i++)
        cout<<h[i].x<<' '<<h[i].y<<'\n';

    return 0;
}