Pagini recente » Cod sursa (job #1857889) | Cod sursa (job #1708954) | Cod sursa (job #605020) | Cod sursa (job #1994085) | Cod sursa (job #1466897)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define NMAX 150000
using namespace std;
ifstream f ("infasuratoare.in") ;
ofstream g ("infasuratoare.out") ;
int n , vf ;
struct elem{double x , y ;} a[NMAX] , stiva[NMAX];
double arie(elem q, elem b , elem c) {
double rez = 0;
rez += q . x * b . y;
rez += q . y * c . x;
rez += b . x * c . y;
rez -= q . x * c . y;
rez -= q . y * b . x;
rez -= b . y * c . x;
return rez / 2;
}
bool comp1(elem a , elem b){
return a . x < b . x || (a . x == b . x && a . y < b . y) ;
}
bool comp2(elem q , elem b){
return arie(q , b , a[1]) < 0 ;
}
int main()
{
f >> n ;
for(int i = 1 ; i <= n ; ++i){
f >> a[i].x >> a[i].y ;
}
sort(a + 1 , a + n + 1 , comp1) ;
sort(a + 2 , a + n + 1 , comp2) ;
stiva[1] = a[1] ;
stiva[2] = a[2] ;
vf = 2 ;
for(int i = 3 ; i <= n ; ++i){
stiva[++vf] = a[i] ;
while(vf > 3 && arie(stiva[vf] , stiva[vf - 1] , stiva[vf - 2]) < 0){
stiva[vf - 1] = stiva[vf] ;
--vf ;
}
}
g << vf << '\n' ;
for(int i = vf ; i >= 1 ; --i){
g << setprecision(13) << fixed << stiva[i] . x << " " << stiva[i] . y << '\n' ;
}
return 0;
}