Pagini recente » Cod sursa (job #1625302) | Cod sursa (job #533566) | Cod sursa (job #872192) | Cod sursa (job #2669087) | Cod sursa (job #1587515)
#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 ;} v[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 , v[1]) < 0;
}
int main()
{
f >> n;
for(int i = 1 ; i <= n ; ++i) {
f >> v[i].x >> v[i].y;
}
sort(v + 1 , v + n + 1 , comp1);
sort(v + 2 , v + n + 1 , comp2);
stiva[1] = v[1];
stiva[2] = v[2];
vf = 2;
for(int i = 3 ; i <= n ; ++i) {
stiva[++vf] = v[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(10) << fixed << stiva[i] . x << " " << stiva[i] . y << '\n';
}
return 0;
}