Cod sursa(job #932984)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 29 martie 2013 14:40:04
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define nmax 120100
using namespace std;

struct punct{double X,Y;}Punct[nmax];

class stack {

    public:
        int Top;
        punct St[nmax];

    public:
        stack() {Top=0;}
        void push(punct A) {
            St[++Top]=A;
            }
        void pop() {
            --Top;
            }
        int size() {
            return Top;
            }
        punct operator[] (int i) {
            return St[i];
            }

};

stack Stack;
int N;

int Det(punct A,punct B,punct C) {

    return A.X*B.Y + A.Y*C.X + B.X*C.Y - B.Y*C.X - A.X*C.Y - B.X*A.Y;

}
bool compare(punct A,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].X < Punct[P].X || (Punct[i].X == Punct[P].X && Punct[i].Y < Punct[P].Y) )
            P=i;

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

    Stack.push(Punct[1]);
    Stack.push(Punct[2]);

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

        while( Stack.size()>1 && Det(Stack[Stack.Top-1], Stack[Stack.Top], Punct[i]) > 0 )
            Stack.pop();

        Stack.push(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<<Stack.size()<<'\n';

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

    out.close();

}
int main() {

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

    return 0;

}