Pagini recente » Cod sursa (job #2217598) | Cod sursa (job #3179689) | Cod sursa (job #1802243) | Cod sursa (job #1769017) | Cod sursa (job #2563701)
#define eps 0.000000000001d
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct
{
double x, y;
bool operator < (const Punct& other) const
{
if (fabs(y - other.y) < eps)
return x < other.x;
return y < other.y;
}
};
int n, top, Stk[120001];
Punct A[120001];
double Prod(const Punct& p1, const Punct& p2, const Punct& p3)
{
return (p1.x - p2.x) * (p1.y - p3.y) - (p1.x - p3.x) * (p1.y - p2.y);
}
bool SortF(const Punct& p1, const Punct& p2)
{
return Prod(A[1], p1, p2) > 0.0d;
}
void Solve()
{
Stk[1] = 1, Stk[2] = 2;
top = 2;
for (int i = 3; i <= n; ++i)
{
while (Prod(A[Stk[top - 1]], A[Stk[top]], A[i]) < 0)
--top;
Stk[++top] = i;
}
}
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i)
{
fin >> A[i].x >> A[i].y;
if (A[i] < A[1])
swap(A[i], A[1]);
}
sort(A + 2, A + n + 1, SortF);
Solve();
for (int i = 1; i <= top; ++i)
fout << fixed << setprecision(7) << A[Stk[i]].x << " " << A[Stk[i]].y << '\n';
return 0;
}