Cod sursa(job #3358861)

Utilizator LicaMihaiIonutLica Mihai- Ionut LicaMihaiIonut Data 20 iunie 2026 23:22:46
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 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 f("infasuratoare.in");
ofstream g("infasuratoare.out");
#define cin f
#define cout g
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;
}