Pagini recente » Cod sursa (job #2667033) | Cod sursa (job #826812) | Cod sursa (job #473159) | Cod sursa (job #1229603) | Cod sursa (job #2563683)
#define MAX_N 140000
//#define x first
//#define y second
#include <fstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <utility>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x, y;
bool operator< (const punct& other) const
{
if (y < other.y) { return true; }
return x < other.x;
}
} A[MAX_N + 1];
//pair<double, double> A[MAX_N + 1];
//typedef pair<double, double> punct;
int n, top, Stk[MAX_N + 1];
double ArieCuSemn(const punct& a, const punct& b, const punct& c);
int main()
{
fin >> n;
int indice = -1;
for (int i = 1; i <= n; ++i)
{
fin >> A[i].x >> A[i].y;
if ((indice == -1) || (A[i] < A[indice]))
{
indice = i;
}
}
swap(A[1], A[indice]);
sort(A + 2, A + n + 1, [] (const punct& p1, const punct& p2) { return ArieCuSemn(A[1], p1, p2) >= 0.0; });
Stk[1] = 1;
Stk[2] = 2;
top = 2;
for (int i = 3; i <= n; ++i)
{
while ((top >= 2) && (ArieCuSemn(A[Stk[top - 1]], A[Stk[top]], A[i]) <= 0.0))
{
--top;
}
Stk[++top] = i;
}
fout << top << '\n';
for (int i = 1; i <= top; ++i)
{
fout << fixed << setprecision(numeric_limits<double>::digits10 + 1) << A[Stk[i]].x << ' ' << A[Stk[i]].y << '\n';
}
fin.close();
fout.close();
return 0;
}
double ArieCuSemn(const punct& a, const punct& b, const punct& c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}