Cod sursa(job #557000)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 16 martie 2011 13:40:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

#define x first
#define y second

const char Input[] = "infasuratoare.in";
const char Output[] = "infasuratoare.out";

const int Inf = 0x3f3f3f3f;

int N;
vector <int> st;
vector < pair <double, double> > P;

double Pnt( pair <double, double> A, pair <double, double> B ) {

    if( A.x == B.x )
        return Inf;

    return (A.y - B.y) / (A.x - B.x);
}

double Sgn( pair <double, double> A, pair <double, double> B, pair <double, double> C ) {

    return A.x * B.y + C.x * A.y + B.x * C.y - (C.x * B.y + B.x * A.y + A.x * C.y);
}

struct Cmp {

    bool operator()( pair <double, double> A, pair <double, double> B ) {

        return Pnt( P[0], A ) < Pnt( P[0], B );
    }
};

int main() {

    ifstream fin( Input );
    ofstream fout( Output );

    int i;

    fin >> N;
    P.resize( N );
    for( i = 0; i < N; ++i ) {

        fin >> P[i].x >> P[i].y;
        if( P[i].x < P[0].x )
            swap( P[i], P[0] );
        else if( P[i].x == P[0].x && P[i].y < P[0].y )
            swap( P[i], P[0] );
    }

    sort( P.begin() + 1, P.end(), Cmp() );
    for( i = 0; i < N; ++i ) {

        while( st.size() > 2 && Sgn( P[st[st.size() - 2]], P[st[st.size() - 1]], P[i] ) < 0 )
            st.pop_back();
        st.push_back( i );
    }

    fout << st.size() << "\n";
    for( i = 0; i < (int)st.size(); ++i )
        fout << fixed << P[st[i]].x << " " << P[st[i]].y << "\n";

    fin.close();
    fout.close();

    return 0;
}