Pagini recente » Cod sursa (job #2620465) | Cod sursa (job #1966279) | Cod sursa (job #2663493) | Cod sursa (job #58986) | Cod sursa (job #2789349)
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const int NMAX = 12e4;
struct pct {
ld x, y;
} a[NMAX + 1];
int n;
inline ld crossProd(const pct X, const pct Y, const pct Z) {
return (Y.y - X.y) * (Z.x - X.x) - (Y.x - X.x) * (Z.y - X.y);
}
inline int secondToLast(stack<int> ST) {
ST.pop();
return ST.top();
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
int firstPoint = 0;
for(int i = 1; i <= n; ++i) {
scanf("%Le%Le", &a[i].x, &a[i].y);
if(!firstPoint || (a[i].x < a[firstPoint].x || (a[i].x == a[firstPoint].x && a[i].y < a[firstPoint].y)))
firstPoint = i;
}
swap(a[firstPoint], a[1]);
sort(a + 2, a + n + 1, [](const pct X, const pct Y) {
return crossProd(a[1], X, Y) > 0;
});
stack<int> ans;
ans.push(1), ans.push(2);
for(int i = 3; i <= n; ++i) {
while(ans.size() >= 2 && crossProd(a[secondToLast(ans)], a[ans.top()], a[i]) < 0)
ans.pop();
ans.push(i);
}
cout << ans.size() << "\n";
while(!ans.empty())
cout << fixed << setprecision(12) << a[ans.top()].x << " " << a[ans.top()].y << "\n",
ans.pop();
return 0;
}