Pagini recente » Cod sursa (job #1503483) | Cod sursa (job #3246234) | Cod sursa (job #2380574) | Cod sursa (job #2582051) | Cod sursa (job #1184692)
#include <fstream>
#include <climits>
#include <cfloat>
#include <algorithm>
using namespace std;
struct punct
{
double x, y;
};
punct puncte[120003];
punct stiva[120003];
double cp(punct &a, punct &b , punct &c)
{
return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
bool cmp(punct &a, punct &b)
{
if (cp(puncte[0], a, b) < 0)
{
return true;
}
return false;
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n , i , poz;
punct extremaStanga;
extremaStanga.x = DBL_MAX;
extremaStanga.y = DBL_MAX;
in >> n;
for (i = 0; i < n; i++)
{
in >> puncte[i].x >> puncte[i].y;
if (puncte[i].x < extremaStanga.x)
{
extremaStanga.x = puncte[i].x;
extremaStanga.y = puncte[i].y;
poz = i;
}
else
{
if (puncte[i].x == extremaStanga.x)
{
if (puncte[i].y < extremaStanga.y)
{
extremaStanga.x = puncte[i].x;
extremaStanga.y = puncte[i].y;
}
}
}
}
swap(puncte[0], puncte[poz]);
sort(puncte + 1, puncte + n, cmp);
stiva[0] = puncte[0];
stiva[1] = puncte[1];
poz = 1;
for (i = 2; i < n; i++)
{
while (poz >= 1 && cp(stiva[poz - 1], stiva[poz], puncte[i]) > 0)
poz--;
stiva[++poz] = puncte[i];
}
out.setf(ios::floatfield, ios::fixed);
out.precision(9);
out << poz + 1 << '\n';
for (i = poz; i >= 0; i--)
{
out << stiva[i].x << ' ' << stiva[i].y << '\n';
}
return 0;
}