Pagini recente » Cod sursa (job #471294) | Cod sursa (job #1580262) | Cod sursa (job #1255899) | Cod sursa (job #1514912) | Cod sursa (job #2822913)
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int NMAX = 12e4;
typedef long double ld;
struct pct {
ld x, y;
} a[NMAX + 1];
int n, ans[NMAX + 1], ansl;
inline ld crossProd(const pct A, const pct B, const pct C) {
return -(A.x * B.y + C.x * A.y + B.x * C.y - C.x * B.y - A.x * C.y - B.x * A.y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
int firstPct = 1;
for(int i = 1; i <= n; ++i) {
scanf("%Le%Le", &a[i].x, &a[i].y);
if(a[firstPct].y > a[i].y || (a[firstPct].y == a[i].y && a[firstPct].x > a[i].y))
firstPct = i;
}
swap(a[firstPct], a[1]);
sort(a + 2, a + n + 1, [](const pct A, const pct B) {
return crossProd(a[1], A, B) > 0;
});
ans[++ansl] = 1, ans[++ansl] = 2;
for(int i = 3; i <= n; ++i) {
while(ansl >= 2 && crossProd(a[ans[ansl - 1]], a[ans[ansl]], a[i]) < 0)
--ansl;
ans[++ansl] = i;
}
printf("%d\n", ansl);
for(int i = ansl; i; --i)
cout << fixed << setprecision(12) << a[ans[i]].x << " " << a[ans[i]].y << "\n";
return 0;
}