Pagini recente » Cod sursa (job #440844) | Cod sursa (job #662238) | Cod sursa (job #2271570) | Cod sursa (job #2982076) | Cod sursa (job #1566387)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#define nmax 120001
using namespace std;
struct point {
double x, y;
} P[nmax];
int n;
int st[nmax];
int stackSize;
bool viz[nmax];
bool cmp(point a, point b)
{
if (a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
double det(point a, point b, point c)
{
return (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
}
int main()
{
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
/*
8
2.0 0.0
0.0 2.0
1.0 3.0
0.0 4.0
3.0 3.0
2.0 6.0
4.0 2.0
4.0 4.0
*/
fi >> n;
for (int i = 1; i <= n; i++)
fi >> P[i].x >> P[i].y;
sort(P+1, P+n+1, cmp);
st[1] = 1;
st[2] = 2;
stackSize = 2;
viz[st[1]] = viz[st[2]] = true;
for (int i = 3; i <= n; i++)
{
while (stackSize > 1 && det(P[ st[stackSize-1] ], P[ st[stackSize] ], P[i]) < 0)
viz[ st[stackSize--] ] = false;
st[++stackSize] = i;
viz[i] = true;
}
for (int i = n; i > 1; i--)
{
if (viz[i])
continue;
while (stackSize > 1 && det(P[ st[stackSize-1] ], P[ st[stackSize] ], P[i]) < 0)
stackSize--;
st[++stackSize] = i;
}
fo << stackSize << "\n";
fo << fixed;
for (int i = 1; i <= stackSize; i++)
fo << setprecision(6) << P[st[i]].x << " " << P[st[i]].y << "\n";
fi.close();
fo.close();
return 0;
}