Cod sursa(job #2764360)

Utilizator BalasaRaduBalasa Radu BalasaRadu Data 20 iulie 2021 16:13:28
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;

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

const int dim=100009;

struct punct{
long double x,y;}v[dim];

punct stiva[dim];
int vf;

long double determinat(punct A,punct B,punct C){
    return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}

bool ccw(punct A,punct B,punct C){
    return determinat(A,B,C)>0;
}

bool cmp(punct A,punct B){
    return ccw(v[1],A,B);
}

signed main(){

    int n;
        fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
        if(v[1].y==v[i].y){
            if(v[1].x>v[1].x)
                swap(v[1],v[i]);
        }
        else{
            if(v[1].y>v[i].y)
                swap(v[1],v[i]);
        }
    }

    sort(v+2,v+n+1,cmp);
    stiva[++vf]=v[1];

    for(int i=2;i<=n;i++){
        while(vf>1&&!ccw(stiva[vf-1],stiva[vf],v[i])){
            vf--;
        }
        stiva[++vf]=v[i];
    }

        fout<<vf<<'\n';
    for(int i=1;i<=vf;i++)
        fout<<fixed<<setprecision(12)<<stiva[i].x<<' '<<stiva[i].y<<'\n';
}