Pagini recente » Cod sursa (job #1385409) | Cod sursa (job #185823) | Cod sursa (job #1387375) | Cod sursa (job #1127983) | Cod sursa (job #2754630)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#define DIM 120005
int n, st[DIM], i, vf, semn;
bool sel[DIM];
struct nanu {
double x, y;
} v[DIM];
static inline bool cmp(nanu a, nanu b) {
return (a.y < b.y || (a.y == b.y && a.x < b.x));
}
static inline int det(double x1, double Y1, double x2, double y2, double x3, double y3) {
int d = (x2 - x1) * (y3 - Y1) - (x3 - x1) * (y2 - Y1);
if(d < 0)
return - 1;
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;
st[++vf] = 2;
sel[2] = 1;
i = 3, semn = 1;
while(sel[1] == 0) {
while(sel[i]) {
if(i == n)
semn = -1;
i += semn;
}
while(vf >= 2 && det(v[st[vf - 1]].x, v[st[vf - 1]].y, v[st[vf]].x, v[st[vf]].y, v[i].x, v[i].y) == -1)
sel[st[vf--]] = 0;
st[++vf] = i;
sel[i] = 1;
}
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;
}