Cod sursa(job #1377229)

Utilizator gerd13David Gergely gerd13 Data 5 martie 2015 20:49:13
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iomanip>
 
#define x first
#define y second
 
using namespace std ;
 
typedef pair <double, double> Pair ;
const int NMAX = 120005 ;
 
ifstream fin("infasuratoare.in") ;
ofstream fout("infasuratoare.out") ;
 
Pair V[NMAX] ;
int st[NMAX] ;
int head, posmin = 1, N;
 
inline double cross_product(const Pair A, const Pair B, const Pair C) {
    return ((A.x * B.y) + (B.x * C.y) + 
    (C.x * A.y) - (A.y * B.x) - (B.y * C.x) 
    - (C.y * A.x)) ; }
 
struct cmp{
    inline bool operator () (const Pair &A, const Pair &B){
        return (cross_product(V[1], A, B) > 0);}
};
 
int main() {
    fin >> N ;
 
    for(int i = 1 ; i <= N ; ++ i) {
        fin >> V[i].x >> V[i].y ;
            if(V[i] < V[posmin])
                posmin = i ; }
 
    swap(V[1], V[posmin]) ;
    sort(V + 1, V + N + 1, cmp()) ;
 
    st[1] = 1 ;
    st[2] = head = 2 ;
 
    for(int i = 3 ; i <= N; ++ i) {
        while(head >= 2 && cross_product(V[i], V[head - 1], V[head]) < 0)
            -- head ;
        st[++ head] = i ; }
 
    fout << head << '\n' ;
    fout << fixed << setprecision(9) ;
 
    for(int i = 1 ; i <= head ; ++ i)
        fout << V[i].x << ' ' << V[i].y << '\n' ;
 
    fin.close() ; fout.close() ;
    return 0 ; }