Pagini recente » Cod sursa (job #11815) | Cod sursa (job #1735210) | Cod sursa (job #1889093) | Cod sursa (job #2659529) | Cod sursa (job #2822908)
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef long double ld;
const int NMAX = 12e4;
struct pct {
ld x, y;
} a[NMAX + 1];
int n, ans[NMAX + 1], ansl;
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);
return -(X.x * Y.y + Z.x * X.y + Y.x * Z.y - Z.x * Y.y - X.x * Z.y - Y.x * X.y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
int firstPoint = 1;
for(int i = 1; i <= n; ++i) {
scanf("%Le%Le", &a[i].x, &a[i].y);
if(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;
});
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;
}
cout << ansl << "\n";
while(ansl)
cout << fixed << setprecision(12) << a[ans[ansl]].x << " " << a[ans[ansl]].y << "\n",
--ansl;
return 0;
}