Pagini recente » Cod sursa (job #176147) | Cod sursa (job #2494985) | Cod sursa (job #1270791) | Cod sursa (job #2519979) | Cod sursa (job #2869643)
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>
#define NMAX 120005
#define EPS 1e-9
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef long double ld;
struct elem {
ld x, y, val;
} a[NMAX], c;
int n, st[NMAX], ans;
inline ld vabs(const ld X) {
return X > 0 ? X : - X;
}
inline bool isEqual(const ld A, const ld B) {
return vabs(A - B) <= EPS;
}
inline ld dist(const elem A, const elem B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
inline ld crossProd(const elem A, const elem B, const elem 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()
{
ios::sync_with_stdio(false);
fin.tie(0); fout.tie(0);
fin >> n;
int primulPct = 1;
for(int i = 1; i <= n; ++i) {
fin >> a[i].x >> a[i].y;
c.x += a[i].x, c.y += a[i].y;
if(a[primulPct].y > a[i].y || (a[primulPct].y == a[i].y && a[primulPct].x > a[i].x)) primulPct = i;
}
c.x /= n, c.y /= n;
swap(a[primulPct], a[1]);
sort(a + 2, a + n + 1, [](const elem A, const elem B) {
return crossProd(a[1], A, B) > 0;
});
st[1] = 1, st[2] = 2, ans = 2;
for(int i = 3; i <= n; ++i) {
while(ans >= 2 && crossProd(a[st[ans - 1]], a[st[ans]], a[i]) < 0)
--ans;
st[++ans] = i;
}
fout << ans << "\n";
for(int i = 1; i <= ans; ++i)
fout << fixed << setprecision(12) << a[st[i]].x << " " << a[st[i]].y << "\n";
return 0;
}