Cod sursa(job #2748526)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 1 mai 2021 12:02:08
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int hull[120005];

struct Point{
    double x,y;
}P1,P2,P3,v[120005];

double cross_product(Point a,Point b,Point c){
    return (a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x);
}

bool ms(Point a,Point b){
    return (cross_product(v[1],a,b)>=0);
}

int main()
{
    int n,mini=1;
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
        if(v[mini].y>v[i].y){
            mini=i;
        }
    }
    swap(v[1],v[mini]);
    sort(v+2,v+n+1,ms);
    v[++n]=v[1];
    hull[1]=1;
    int cnt=1;
    for(int i=1;i<=n;i++){
        while(cnt>1 and cross_product(v[hull[cnt-1]],v[hull[cnt]],v[i])<=0){
            cnt--;
        }
        hull[++cnt]=i;
    }
    cnt--;
    fout<<cnt<<"\n";
    for(int i=1;i<=cnt;i++){
        fout<<fixed<<setprecision(6);
        fout<<v[hull[i]].x<<" "<<v[hull[i]].y<<"\n";
    }
    return 0;
}