Cod sursa(job #1343348)

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

double 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,q,k;
    register double x,y;

    f>>n;
    p=1;
    for(i=1;i<=n;i++){
        f>>x>>y,v[i]=make_pair(x,y);
        if(v[p]>v[i])   p=i;
    }
    swap(v[1],v[p]);

    sort(v+2,v+n+1,cmp);

    S[1]=1,k=2,S[2]=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";
    }
    return 0;
}