Cod sursa(job #2123047)

Utilizator edynator34Nechitoaia George-Edward edynator34 Data 5 februarie 2018 18:58:15
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n,j,i,k;
struct punct{
    double x;
    double y;
} s[120005],v[120005];

int deter(punct a, punct b,punct c){
     return ((a.x*b.y)+(b.x*c.y)+(a.y*c.x)-(b.y*c.x)-(a.x*c.y)-(b.x*a.y));
}

bool comp(punct a, punct b){
    if(deter(v[1],a,b)>0) return true;
    return false;
}
int main()
{
    in>>n;
    in>>v[1].x>>v[1].y;
    j=1;
    for(i=2;i<=n;++i){
        in>>v[i].x>>v[i].y;
        if(v[i].x  <  v[j].x || (v[i].x  ==  v[j].x  &&  v[i].y  <  v[j].y)) j=i;

    }
    swap(v[1],v[j]);
    sort(v+2,v+n+1,comp);
    s[1]=v[1]; s[2]=v[2]; k=2;
    for(i=3;i<=n;++i){
        while(k>=2 && deter(s[k-1],s[k],v[i])<0)k--;
        k++;s[k]=v[i];
    }
    out<<k<<'\n';
    out<<fixed;
    for(i=1;i<=k;++i) out<<setprecision(6)<<s[i].x<<' '<<setprecision(6)<<s[i].y<<'\n';
    return 0;
}