Cod sursa(job #3355100)

Utilizator CiuntuTiberiuCiuntu Tiberiu CiuntuTiberiu Data 21 mai 2026 19:03:32
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct POINT{
    double x,y;
};
POINT v[120005];
POINT LL;
const double eps=1.e-12;

bool compar(POINT P1,POINT P2)
{
    if(P2.y-P1.y <= -eps)
        return 1;
    else
        if(fabs(P2.y-P1.y)<eps && P2.x-P1.x<=-eps)
            return 1;
        else
            return 0;
}

double cp(POINT P1,POINT P2,POINT P3)
{
    return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
}

int ccw(POINT P1,POINT P2,POINT P3)
{
    double product;
    product=cp(P1,P2,P3);
    if(fabs(product)<eps)
        return 0;
    if(product>=eps)
        return 1;
    return -1;
}

bool cmp(POINT A,POINT B)
{
    if(ccw(LL,A,B)==-1)
        return 0;
    return 1;
}

int main()
{
    int n,i,top;
    fin>>n;
    fin>>v[1].x>>v[1].y;
    for(i=2;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        if(compar(v[1],v[i]))
            swap(v[1],v[i]);
    }
    LL=v[1];
    sort(v+2,v+n+1,cmp);
    v[n+1]=LL;

    //Infasuratoarea convexa/Convex Hull
    int h[120005];
    h[1]=1;
    h[2]=2;
    top=2;
    i=3;
    while(i<=n+1)
    {
        if(ccw(v[h[top-1]],v[h[top]],v[i])>0)
        {
            h[++top]=i;
            i++;
        }
        else
            top--;
    }
    top--;
    fout<<top<<"\n";
    for(i=1;i<=top;i++)
    {
        fout<<fixed<<showpoint<<setprecision(6)<<v[h[i]].x<<" "<<v[h[i]].y<<"\n";
    }
    // adaug pct 1, adaug pct 2, de la al treilea verific cum
    // este orientat fata de p1 si p2
    // e in sens trig il adaug, la fel si p4
    // de la p5 face misc in sens orar
    // deci il scot pe p4 din stiva si il adaug pe p5
    // si analizez p2p3p5 si daca e bun il adaug
    // p6 merge il adaug dar la p7 nu merge
    // scot p6, verific p3p5p7
    return 0;
}