Cod sursa(job #2586326)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 20 martie 2020 15:35:44
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

const int MAXN = 120000 + 2;

using namespace std;

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

typedef long double ld;

struct punct{
    ld x,y;
}v[MAXN],stiva[MAXN];

int n,varf;
punct primul_punct;

bool cmp_puncte(punct a,punct b){
    if(a.y < b.y)
        return true;
    if(a.y == b.y)
        return a.x < b.x;
    return false;
}
ld unghi(punct a,punct b){
    return (a.x - b.x) / (a.y - b.y);
}
bool cmp_unghi(punct a,punct b){
    if(unghi(primul_punct,a) > unghi(primul_punct,b))
        return true;
    return false;
}
ld cross(punct a,punct b,punct c){
    ld val = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
    return val;
}

void afis(){
    cout<<"Stiva : "<<"\n";
    for(int i = 1; i <= varf; i++)
        cout<<stiva[i].x<<" "<<stiva[i].y<<"\n";
}


int main()
{
    in>>n;
    for(int i = 1; i <= n; i++)
        in>>v[i].x>>v[i].y;
    sort(v + 1,v + n + 1,cmp_puncte);
    primul_punct = v[1];
    sort(v + 2,v + n + 1,cmp_unghi);
//    for(int i = 2; i <= n; i++){
//        cout<<v[i].x<<" "<<v[i].y<<" cu unghiul : "<<unghi(primul_punct,v[i])<<endl;
//    }
    varf = 2;
    stiva[1] = primul_punct;
    stiva[2] = v[2];
    ///afis();
    /// daca merg unghiul format dintre dreapta determinata de penuiltimul,ultimul si penultimul curent > 180 => nu e ok

    for(int i = 3; i <= n; i++){
        while(varf >= 2 && cross(stiva[varf - 1],stiva[varf],v[i]) < 0){
            varf--;
        }
        stiva[++varf] = v[i];
    }
    out<<varf<<"\n";
    for(int i = 1; i <= varf; i++)
        out<<setprecision(13)<<fixed<<stiva[i].x<<" "<<stiva[i].y<<"\n";



    return 0;
}