Cod sursa(job #1310841)

Utilizator gerd13David Gergely gerd13 Data 7 ianuarie 2015 12:08:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>

///-------------------------------------------------------------------------------------

using namespace std ;

typedef pair<double, double> Pair ;

const int NMAX = 1200005 ;
const int INF = 0x3f3f3f3f ;
const double EPS = 1e-12 ;  

///-------------------------------------------------------------------------------------


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

///-------------------------------------------------------------------------------------


int N;
Pair V[NMAX] ;
bool viz[NMAX] ;
int st[NMAX], vf ;


///-------------------------------------------------------------------------------------

inline void Read()
{
	fin >> N ;
	for(int i = 1 ; i <= N ; ++ i)
	{
		fin >> V[i].first >> V[i].second ; 
	}
}

///-------------------------------------------------------------------------------------

inline double cross(Pair O, Pair A, Pair B)
{
	return (A.first - O.first) * (B.second - O.second) - (B.first - O.first) * (A.second - O.second) ;  
}

inline void Solve()
{
	sort(V + 1, V + N  + 1) ; 

	st[1] = 1 ;
	st[2] = vf = 2 ;
    viz[2] = true ;

    for(int i = 1, p = 1 ; i > 0 ; i = i + (p = (i == N  ? - p : p ) ) )
    {
    	if(viz[i])
    		continue ;
    	while(vf >= 2 && (cross(V[st[vf - 1]], V[st[vf]], V[i])) < EPS )
    		viz[st[vf -- ]] = false ;
    	st[++ vf] = i ;
    	viz[i] = true ; 
    }



}

///-------------------------------------------------------------------------------------

inline void OUT()
{
	fout << vf - 1 << '\n' ;

	fout << fixed << setprecision(9)   ;

	for(int i = 1 ; i < vf ; ++ i)
		fout << V[st[i]].first << " " << V[st[i]].second << '\n' ; 
}


///-------------------------------------------------------------------------------------

int main()
{
	Read() ;
	Solve() ;
	OUT() ; 
	fin.close() ;
	fout.close() ;
	return 0 ;
}