Cod sursa(job #901059)

Utilizator Theorytheo .c Theory Data 28 februarie 2013 23:55:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<fstream>
#include<stack>
#include<algorithm>
#include<iomanip>
#include<cmath>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");


const int Nmax = 120009;
const double Eps = 0.00001;


struct Point{ double x, y;}V[Nmax];


int S[Nmax]; int First = 1; int N;

double Arie(const Point V1,const Point V2,const Point V3){

    return V1.x * V2.y + V2.x * V3.y + V3.x * V1.y - V1.y * V2.x - V2.y * V3.x - V3.y * V1.x;
}

struct cmp{

    bool operator ()(const Point &A,const Point &B)const{
        return Arie(V[1], A, B) <0 ;
    }
};
void Read(){

    fin >> N;

    for(int i = 1; i <= N; ++i){
        fin >> V[i].x >> V[i].y;
        if(V[i].x < V[First].x ||  (fabs(V[i].x - V[First].x) < Eps && V[First].y > V[i].y))
            First = i;
    }
    swap(V[1], V[First]);
    sort(V + 2, V + 1 + N, cmp());
}

void Inf(){
    S[0] = 2; S[1] = 1;S[2] = 2;

    for(int i = 3; i <= N; ++i){
        while(Arie(V[S[S[0] - 1]], V[S[S[0]]], V[i]) > 0 && S[0] >= 2) S[0]--;

        S[++S[0]] = i;
    }

    fout << S[0]<<'\n';
    for(int i = S[0] ; i ; --i)
        fout << fixed<<setprecision(6) << V[S[i]].x <<" "<<V[S[i]].y <<'\n';

}

int main(){

    Read();

    Inf();

    return 0;
}