Cod sursa(job #933006)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 29 martie 2013 15:01:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define nmax 120100
#define punct pair <double,double>
#define X first
#define Y second
using namespace std;

punct Punct[nmax],Stack[nmax];
int N,Top;

inline double Det(const punct &A,const punct &B,const punct &C) {

    return (B.X-A.X) * (C.Y-A.Y) - (B.Y-A.Y) * (C.X-A.X);;

}
inline bool compare(const punct &A,const punct &B) {

    return Det(Punct[1],A,B) < 0;

}
void solve() {

    int i,P;

    P=1;
    for(i=2;i<=N;i++)
        if(Punct[i] < Punct[P])
            P=i;

    swap(Punct[P],Punct[1]);
    sort(Punct+2,Punct+N+1,compare);

    Stack[++Top]=Punct[1];
    Stack[++Top]=Punct[2];

    for(i=3;i<=N;i++) {

        while( Top>=2 && Det(Stack[Top-1], Stack[Top], Punct[i]) >0 )
            Top--;

        Stack[++Top]=Punct[i];

        }

}
void read() {

    ifstream in("infasuratoare.in");
    in>>N;

    for(int i=1;i<=N;i++)
        in>>Punct[i].X>>Punct[i].Y;

    in.close();

}
void write() {

    ofstream out("infasuratoare.out");

    out<<Top<<'\n';

    for(int i=Top;i>=1;i--)
        out<<fixed<<setprecision(12)<<Stack[i].X<<' '<<Stack[i].Y<<'\n';

    out.close();

}
int main() {

    read();
    solve();
    write();

    return 0;

}