Cod sursa(job #2106689)

Utilizator blackmanta45Andrei blackmanta45 Data 16 ianuarie 2018 04:28:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int s[120010],i,poz,h,n;
pair <double,double> v[120010],c;

int cmp (pair<double,double> a, pair <double,double> b){
    if((a.y-c.y)*(b.x-c.x)-(a.x-c.x)*(b.y-c.y)<0)
        return 1;
    else
        return 0;
}

double calc (pair<double,double> a, pair <double,double> b, pair <double,double> c){
    return (b.x-c.x)*(a.y-c.y)-(b.y-c.y)*(a.x-c.x);
}

int main () {
    fin>>n;
    c.x=200000000;
    c.y=200000000;
    for(i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
        if(v[i].x<c.x)
            c=v[i],poz=i;
        else
            if(v[i].x==c.x && v[i].y<c.y)
                c=v[i],poz=i;
    }
    v[poz]=v[1];
    v[1]=c;
    sort(v+2,v+n+1,cmp);
    s[1]=1;
    s[2]=2;
    h=2;
    for(i=3;i<=n;i++){
        if(calc(v[s[h]],v[i],v[s[h-1]])<=0)
            s[++h]=i;
        else{
            while(calc(v[s[h]],v[i],v[s[h-1]])>0)
                h--;
            s[++h]=i;
        }
    }
    fout<<h<<"\n";
    for(i=1;i<=h;i++)
        fout<<setprecision(6)<<fixed<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
}