Pagini recente » Cod sursa (job #2840845) | Cod sursa (job #3254750) | Cod sursa (job #2453955) | Cod sursa (job #2953977) | Cod sursa (job #1623569)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <iostream>
#define x first
#define y second
using namespace std ;
const int NMAX = 120005 ;
const double e = 1e-12 ;
ifstream fin("infasuratoare.in") ;
ofstream fout("infasuratoare.out") ;
pair <double, double> V[NMAX] ;
bool use[NMAX] ;
int st[NMAX], head, N ;
double cross_product(pair <double, double> O, pair <double, double> A, pair <double, double> 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) ;
int p = 1 ;
st[1] = 1 ;
st[2] = head = 2 ;
use[2] = 1;
for(int i = 1 ; i > 0 ; i = i + p)
{
if(i == N)
p = -1 ;
if(!use[i] && cross_product(V[st[head - 1]], V[st[head]], V[i]) < e)
use[st[head --]] = 0 ;
st[++head] = i ;
use[i] = 1 ;
}
fout << head - 1 <<'\n';
fout << fixed << setprecision(9) ;
for(int i = 1 ; i < head; ++ i)
fout << V[st[i]].x << ' ' << V[st[i]].y << '\n' ;
fin.close() ;
fout.close() ;
return 0 ;
}