Cod sursa(job #3346172)

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

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

void citire()
{
    fin>>N;

    for(int i=1; i<=N; i++)
    {
        fin>>v[i].x>>v[i].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();

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


    int P=start;
    M=0;
    do
    {
        M++;
        hull[M].x=v[P].x;
        hull[M].y=v[P].y;

        int next=(P+1)%N;
        for(int i=1; i<=N; i++)
        {
            if(arie(v[P],v[next],v[i])<0)
            {
                next=i;
            }
        }
        P=next;

    }while(P!=start);

    fout<< M << "\n";

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

    return 0;
}