Pagini recente » Cod sursa (job #2767319) | Cod sursa (job #339367) | Cod sursa (job #1646250) | Cod sursa (job #2665495) | Cod sursa (job #1310841)
#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 ;
}