Pagini recente » Cod sursa (job #2941238) | Cod sursa (job #2183563) | Cod sursa (job #1135134) | Cod sursa (job #2170558) | Cod sursa (job #2869581)
#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;
} 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;
for(int i = 1; i <= n; ++i)
fin >> a[i].x >> a[i].y,
c.x += a[i].x, c.y += a[i].y;
c.x /= n, c.y /= n;
sort(a + 1, a + n + 1, [](const elem A, const elem B) {
const ld crtA = atan2(A.y - c.y, A.x - c.x),
crtB = atan2(B.y - c.y, B.x - c.x);
if(isEqual(crtA, crtB)) return dist(A, c) > dist(B, c);
return crtA < crtB;
});
a[++n] = a[1];
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;
}
--ans;
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;
}