Cod sursa(job #3291719)

Utilizator stanciuvalentinStanciu-Tivlea Valentin Gabriel stanciuvalentin Data 5 aprilie 2025 13:35:42
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct puncte{
    double x,y;
}v[120200];

int n,k;
double x,y,minx=1000000020,miny=1000000020;
puncte rez[120200];

int cadran(double x,double y){
    if(x>=0 and y>=0)
        return 1;
    return 2;
}

double det(double X1,double Y1,double X2,double Y2,double X3,double Y3){
    return (X2-X1)*(Y3-Y1)-(Y2-Y1)*(X3-X1);
}

double dist(double X1,double Y1,double X2,double Y2){
    return (X2-X1)*(X2-X1)+(Y2-Y1)*(Y2-Y1);
}

double detpii(puncte a,puncte b,puncte c){
    return det(a.x,a.y,b.x,b.y,c.x,c.y);
}

bool compare(puncte a,puncte b){
    double X1=a.x, Y1=a.y;
    double X2=b.x, Y2=b.y;
    if(cadran(X1,Y1)==cadran(X2,Y2))
    {
        double d=det(0,0,X1,Y1,X2,Y2);
        if(d==0)
            if(cadran(X1,Y1)==1)
                return dist(0,0,X1,Y1)<dist(0,0,X2,Y2);
            else
                return dist(0,0,X1,Y1)>dist(0,0,X2,Y2);
        return (d>0);
    }
    return cadran(X1,Y1)<cadran(X2,Y2);
}

int32_t main()
{
    f>>n;
    for(int i=1; i<=n; i++)
    {
        f>>x>>y, v[i]={x,y};
        if(y<miny)
            miny=y, minx=x;
        else if(y==miny)
            minx=min(minx,x);
    }
    for(int i=1; i<=n; i++)
        v[i].x-=minx, v[i].y-=miny;
    sort(v+1,v+n+1,compare);
    rez[1]=v[1], rez[2]=v[2], k=2;
    for(int i=3; i<=n; i++)
    {
        while(k>=2 and detpii(rez[k-1],rez[k],v[i])<=0)
            k--;
        rez[++k]=v[i];
    }
    while(detpii(rez[1],rez[k-1],rez[k])==0)
        k--;
    g<<k<<'\n';
    for(int i=1; i<=k; i++)
        g<<fixed<<setprecision(6)<<rez[i].x+minx<<' '<<rez[i].y+miny<<'\n';
    return 0;
}
/*
4
0 1
0 0
-2 2
-1 1
*/