Cod sursa(job #923727)

Utilizator Theorytheo .c Theory Data 23 martie 2013 20:04:17
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include<fstream>
#include<stack>
#include<algorithm>
#include<iomanip>
#include<cmath>

using namespace std;

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


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


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;

}

double Distance(const Point &P1, const Point P2){

    return sqrt( (P1.x - P2.x) * (P1.x - P2.x) + (P1.y - P2.y) * (P1.y - P2.y));
}

struct cmp{

    bool operator ()(const Point &A,const Point &B)const{
        double Aria = Arie(V[1], A, B);

        if(fabs(Aria)<= Eps)
            return Distance(V[1], A) < Distance(V[1], B);

        return Aria < 0;
    }
};
void Read(){

    fin >> N;

    for(int i = 1; i <= N; ++i){
        fin >> V[i].x >> V[i].y;
        if(V[i].y < V[First].y ||  (fabs(V[i].y - V[First].y) <= Eps && V[First].x > V[i].x))
            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(S[0] > 1 && Arie(V[S[S[0] - 1]], V[S[S[0]]], V[i]) > 0)
        S[0]--;

        S[++S[0]] = i;
    }
    fout << S[0]<<'\n';

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


}

int main(){

    Read();

    Inf();

    return 0;
}