Pagini recente » Cod sursa (job #3175501) | Cod sursa (job #349231) | Cod sursa (job #1426368) | Cod sursa (job #2575763) | Cod sursa (job #2339485)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
const int NMAX = 120005;
struct punct
{
long double x, y;
};
bool operator <(const punct &a, const punct &b)
{
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
int n;
punct P[NMAX], zeu;
punct stiva[NMAX];
int k;
long double dist(punct A, punct B)
{
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
long double unghi(punct A, punct B)
{
if (B.y < A.y)
return (B.x - A.x) / dist(A, B);
else
return 1 + (B.y - A.y) / dist(A, B);
}
bool grhm(punct A, punct B)
{
if (A.x == zeu.x && A.y == zeu.y)
return 1;
if (B.x == zeu.x && B.y == zeu.y)
return 0;
return unghi(zeu, A) > unghi(zeu, B);
}
int verifica(punct A, punct B, punct C)
{
return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
}
int main()
{
fi >> n;
zeu.x = zeu.y = 1e10;
for (int i = 1; i <= n; i++)
{
fi >> P[i].x >> P[i].y;
zeu = min(zeu, P[i]);
}
sort(P + 1, P + n + 1, grhm);
stiva[++k] = P[1];
for (int i = 2; i <= n; i++)
{
while (k > 1 && verifica(stiva[k - 1], stiva[k], P[i]) > 0)
k--;
stiva[++k] = P[i];
}
fo << k << "\n";
for (int i = k; i >= 1; i--)
fo << fixed << setprecision(20) << stiva[i].x << " " << stiva[i].y << "\n";
return 0;
}