Pagini recente » Cod sursa (job #19159) | Cod sursa (job #133659) | Cod sursa (job #1928249) | Cod sursa (job #2461824) | Cod sursa (job #2756038)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#define DIM 120005
const double eps = 0.000000000001;
int n, i, st[DIM], sel[DIM], vf, semn;
struct nanu {
double x, y;
} v[DIM];
static inline double det(nanu a, nanu b, nanu c) {
double d = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
if(d < 0)
return -1;
return 1;
}
static inline bool cmp(nanu a, nanu b) {
if(a.y - b.y < eps)
return 1;
}
int main() {
cin >> n;
for(i = 1; i <= n; i++)
cin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
st[++vf] = 1; ///indicele primului punct;
st[++vf] = 2;
sel[2] = 1;
i = 3, semn = 1;
while(!sel[1]) {
while(sel[i] != 0) {
if(i == n)
semn *= -1;
i += semn;
}
while(vf >= 2 && det(v[st[vf - 1]], v[st[vf]], v[i]) == -1)
sel[st[vf--]] = 0;
sel[i] = 1;
st[++vf] = i;
}
cout << vf - 1 << '\n';
for(i = 1; i < vf; i++)
cout << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';
return 0;
}