Cod sursa(job #3346218)

Utilizator Gabriel_DaescuDaescu Gabriel Florin Gabriel_Daescu Data 12 martie 2026 21:01:58
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#define NMAX 120009
using namespace std;
ifstream  fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N,M;

struct punct
{
    double x,y;
} v[NMAX],hull[2*NMAX];

void citire()
{
    fin>>N;

    for(int i=0; i<N; i++)
    {
        fin>>v[i].x>>v[i].y;
    }
}

bool cmp(punct A, punct B)
{
    if(A.x!=B.x)
    {
        return A.x<B.x;
    }
    else
    {
        return A.y<B.y;
    }
}

double arie(punct A, punct B, punct C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

int main()
{
    citire();

    sort(v,v+N,cmp);

    for(int i=0; i<N; i++)
    {
        while(M>=2 && arie(hull[M-2],hull[M-1],v[i])<=0)
        {
            M--;
        }
        hull[M++]=v[i];
    }

    for(int i=N-1,j=M+1; i>0; i--)
    {
        while(M>=j && arie(hull[M-2],hull[M-1],v[i-1])<=0)
        {
            M--;
        }
        hull[M++]=v[i-1];
    }


    M--;

    fout<< M << "\n";

    for(int i=0; i<M; i++)
    {
        fout<< fixed << setprecision(6) << hull[i].x << " " << hull[i].y << "\n";
    }

    return 0;
}