Pagini recente » Cod sursa (job #1170004) | Cod sursa (job #761595) | Cod sursa (job #552325) | Cod sursa (job #1742929) | Cod sursa (job #1373675)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std ;
typedef pair <double, double> Pair ;
const int NMAX = 120005 ;
const int INF = 0x3f3f3f3f ;
const double EPS = 1e-12 ;
ifstream fin("infasuratoare.in") ;
ofstream fout("infasuratoare.out") ;
int N ;
Pair V[NMAX] ;
bool use[NMAX] ;
int vf, st[NMAX] ;
bool cross_product(Pair O, Pair A, Pair B)
{
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y) ;
}
int main()
{
fin >> N ;
for(int i = 1 ; i <= N ; ++ i)
{
fin >> V[i].first >> V[i].second ;
}
sort(V + 1, V + N + 1) ;
st[1] = 1 ;
st[2] = vf = 2 ;
use[2] = 1 ;
for(int i = 1, p = 1 ; i > 0 ; i = i +( p = (i == N ? -p : p)))
if(!use[i])
{
while(vf >= 2 && (cross_product(V[st[vf - 1]], V[st[vf]], V[i]) < EPS))
use[st[vf --]] = 0 ;
st[ ++ vf] = i ;
use[i] = 1 ;
}
fout << vf - 1 << '\n' ;
fout << fixed << setprecision(9) ;
for(int i = 1 ; i < vf ; ++ i)
fout << V[st[i]].x << ' ' << V[st[i]].y << '\n' ;
fout << '\n' ;
fin.close() ;
fout.close() ;
return 0 ;
}