Cod sursa(job #3346173)

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

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

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);
}

bool cmp(punct A, punct B)
{
    double val=arie(v[start],A,B);

    if(val==0)
    {
        double d1=(A.x-v[start].x)*(A.x-v[start].x)+(A.y-v[start].y)*(A.y-v[start].y);
        double d2=(B.x-v[start].x)*(B.x-v[start].x)+(B.y-v[start].y)*(B.y-v[start].y);
        return d1<d2;
    }

    return val>0;
}

void citire()
{
    fin>>N;

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

int main()
{
    citire();

    start=1;
    for(int i=2; i<=N; i++)
    {
        if(v[i].x<v[start].x || (v[i].x==v[start].x && v[i].y<v[start].y))
        {
            start=i;
        }
    }

    M=0;
    swap(v[1],v[start]);
    start=1;
    sort(v+2,v+N+1,cmp);

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

    fout<< M << "\n";

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

    return 0;
}