Cod sursa(job #1343333)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 15 februarie 2015 12:34:36
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define DIM 130010
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,m;
int S[DIM];
double minim=1000000000;
pair<double,double> v[DIM];

int det(const pair<double,double> &a,const pair<double,double> &b,const pair<double,double> &c){
    return (b.first-a.first)*(c.second-a.second)-(c.first-a.first)*(b.second-a.second);
}

int cmp(const pair<double,double> a,const pair<double,double> b){
    return (det(v[1],a,b)>0);
}

int main(void){
    register int i,j,p,k;

    f>>n;
    for(i=1;i<=n;i++){
        f>>v[i].first>>v[i].second;
        if(v[i].second<minim)
            minim=v[i].second,p=i;
    }
    swap(v[1],v[p]);
    sort(v+1,v+n+1,cmp);

    S[1]=1,S[2]=2,k=2;
    for(i=3;i<=n;i++){
        while(k>1 && det(v[S[k-1]],v[S[k]],v[i])<=0)
            k--;
        S[++k]=i;
    }

    g<<k<<"\n";
    for(i=1;i<=k;i++)
        g<<setprecision(9)<<fixed<<v[S[i]].first<<" "<<v[S[i]].second<<"\n";
    f.close();
    g.close();
    return 0;
}