Pagini recente » Cod sursa (job #1767136) | Cod sursa (job #3175661) | Cod sursa (job #1237172) | Cod sursa (job #2601313) | Cod sursa (job #1894837)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct {
double x, y;
};
bool cmp (punct a, punct b) {
if (a.x < b.x or (a.x == b.x and a.y < b.y))
return true;
return false;
}
bool semn (punct a, punct b, punct c) {
if ((a.x*b.y + b.x*c.y + a.y*c.x - b.y*c.x - a.x*c.y - b.x*a.y) >= 0)
return true;
return false;
}
punct a[101], st[1001];
int n, sf = 2;
int main () {
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
fi >> n;
for (int i = 1; i <= n; i++)
fi >> a[i].x >> a[i].y;
sort (a+1, a+n+1, cmp);
st[1] = a[1], st[2] = a[2];
for (int i = 3; i <= n; i++) {
while (sf > 1 and !semn(st[sf-1], st[sf], a[i]))
sf--;
st[++sf] = a[i];
}
for (int i = n-1; i >= 1; i--) {
while (!semn(st[sf-1], st[sf], a[i]))
sf--;
st[++sf] = a[i];
}
fo << sf-1 << '\n';
int xmin = 2e9, ymin = 2e9, inc = 1;
for (int i = 1; i <= sf-1; i++)
if (st[i].y < ymin or (st[i].y == ymin and st[i].x < xmin))
ymin = st[i].y, xmin = st[i].x, inc = i;
fo << fixed << setprecision(6);
for (int i = inc; i <= sf-1; i++)
fo << st[i].x << ' ' << st[i].y << '\n';
if (inc != 1)
for (int i = 1; i <= inc-1; i++)
fo << st[i].x << ' ' << st[i].y << '\n';
return 0;
}