Cod sursa(job #2955483)

Utilizator Silviu_StefanStefan Silviu Silviu_Stefan Data 17 decembrie 2022 10:25:16
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;
const double eps=10e-14;
struct punct{
    double x,y;
}v[120005];
int indice=-1;
double cp(punct p1,punct p2,punct p3)
{
    return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
int ccw(punct p1,punct p2,punct p3)
{
    if(fabs(cp(p1,p2,p3))<eps){return 0;}
    if(cp(p1,p2,p3)>=eps){return 1;}
    return -1;
}
bool cmp(punct p1,punct p2)
{
    return ccw(v[indice],p1,p2)>0;
}
int stiva[120005];
int main()
{
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    int n;fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
    }
    int miny=1000000005,minx=1000000005;
    for(int i=1;i<=n;i++){
        if(v[i].y<miny){
            indice=i;miny=v[i].y;minx=v[i].x;
        }
        else if(v[i].y==miny&&v[i].x<minx){
            indice=i;miny=v[i].y;minx=v[i].x;
        }
    }
    swap(v[1],v[indice]);indice=1;
    sort(v+2,v+n+1,cmp);
    stiva[1]=1;stiva[2]=2;int pozstiva=2;
    for(int i=3;i<=n;i++){
        while(pozstiva>=2&&ccw(v[stiva[pozstiva-1]],v[stiva[pozstiva]],v[i])<=0){
            pozstiva--;
        }
        pozstiva++;stiva[pozstiva]=i;
    }
    fout<<pozstiva<<'\n';
    for(int i=1;i<=pozstiva;i++){
        fout<<fixed<<setprecision(6)<<v[stiva[i]].x<<" ";
        fout<<fixed<<setprecision(6)<<v[stiva[i]].y<<'\n';
    }
    return 0;
}