Pagini recente » Cod sursa (job #1788005) | Cod sursa (job #111089) | Cod sursa (job #1307481) | Cod sursa (job #104902) | Cod sursa (job #2106312)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <queue>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int Nmax = 120005;
int n, varf, nod;
bool viz[Nmax];
struct punct
{
double x;
double y;
}v[Nmax];
vector<int> Q(Nmax);
vector<int> R(Nmax);
int intoarcere (punct P0, punct P1, punct P2)
{
return (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y);
}
bool cmp(punct A,punct B)
{
if(A.y == B.y)return A.x < B.x;
return A.y < B.y;
}
int main()
{
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[1] = 1;
viz[2] = 1;
for (int i = 3; i <= n; i++)
{
int val = intoarcere (v[Q[varf - 1]], v[Q[varf]], v[i]);
if (val == 0)
{
viz[Q[varf]] = 0;
varf--;
Q[++varf] = i;
viz[i] = 1;
}
else
if (val > 0)
Q[++varf] = i, viz[i] = 1;
else
{
while (val <= 0 && varf > 1)
{
viz[Q[varf]] = 0;
varf--;
val = intoarcere(v[Q[varf - 1]], v[Q[varf]], v[i]);
}
Q[++varf] = i;
viz[i] = 1;
}
}
for (int i = n - 1; i >= 1; i--)
{
if (viz[i] == 1) continue;
int val = intoarcere (v[Q[varf - 1]], v[Q[varf]], v[i]);
if (val == 0)
{
viz[Q[varf]] = 0;
varf--;
Q[++varf] = i;
viz[i] = 1;
}
else
if (val > 0)
Q[++varf] = i, viz[i] = 1;
else
{
while (val <= 0 && varf > 1)
{
viz[Q[varf]] = 0;
varf--;
val = intoarcere(v[Q[varf - 1]], v[Q[varf]], v[i]);
}
Q[++varf] = i;
viz[i] = 1;
}
}
out << varf << '\n';
for (int i = 1; i <= varf; i++)
out << fixed << setprecision(12) << v[Q[i]].x << ' ' << v[Q[i]].y << '\n';
}