Cod sursa(job #1295753)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 20 decembrie 2014 09:42:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#define nmax 120010
#define x first
#define y second
#include <algorithm>
#include <iomanip>
using namespace std;

long long n;
typedef pair<double,double> point;
point v[nmax];
point stk[nmax];

inline double slope(point x,point y,point c){
    return (y.x - x.x)*(c.y - x.y) - (y.y - x.y)*(c.x - x.x);
}

inline bool cmp(point x1,point x2){
return slope(v[1],x1,x2) < 0;
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
void read(){
    fin>>n;
    for(long i = 1;i <= n;i++){
        fin>>v[i].x>>v[i].y;
    }
}

void convex_hull(){
    int ps = 1;
    for(long i = 2;i <= n;i++)
        if(v[i]<v[ps])
            ps = i;
    swap(v[ps],v[1]);
    sort(v+2,v+n+1,cmp);
   stk[1] = v[1];
   stk[2] = v[2];
    int ms = 2;
    for(long i = 3;i <= n;i++){
        while(ms >= 2 && slope(stk[ms-1],stk[ms],v[i]) > 0)--ms;
        stk[++ms] = v[i];
    }
    fout<<fixed;
   fout<<ms<<"\n";
    for(ms;ms;ms--)fout<<setprecision(9)<<stk[ms].x<<" "<<stk[ms].y<<"\n";
}

int main()
{
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    read();
    convex_hull();


    return 0;
}