Pagini recente » Cod sursa (job #1897980) | Cod sursa (job #2084736) | Cod sursa (job #1760197) | 7312 | Cod sursa (job #2107263)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int Nmax = 120005;
struct punct
{
double x;
double y;
}v[Nmax];
bool cmp (punct A, punct B)
{
if(A.y == B.y) return A.x < B.x;
return A.y < B.y;
}
double intoarcere (int P0, int P1, punct P2)
{
return (v[P1].x - v[P0].x) * (P2.y - v[P0].y) - (P2.x - v[P0].x) * (v[P1].y - v[P0].y);
}
int main()
{
int n, varf = 0;
vector<int> Q(Nmax);
vector<bool> viz(Nmax);
in >> n;
for (int i = 1; i <= n; i++)
in >> v[i].x >> v[i].y;
sort (v + 1, v + n + 1, cmp);
Q[++varf] = 1;
Q[++varf] = 2;
viz[2] = 1;
for (int i = 3; i <= n; i++)
{
while (varf > 1 && intoarcere(Q[varf - 1], Q[varf], v[i]) <= 0)
{
viz[Q[varf]] = 0;
varf--;
}
viz[i] = 1;
Q[++varf] = i;
}
const int nr = varf;
for (int i = n - 1; i >= 1; i--)
{
if (viz[i]) continue;
while (varf > nr && intoarcere(Q[varf - 1], Q[varf], v[i]) <= 0)
{
viz[Q[varf]] = 0;
varf--;
}
viz[i] = 1;
Q[++varf] = i;
}
out << varf - 1 << '\n';
for (int i = 1; i < varf; i++)
out << fixed << setprecision(12) << v[Q[i]].x << ' ' << v[Q[i]].y << '\n';
return 0;
}