Pagini recente » Cod sursa (job #344259) | Cod sursa (job #339613) | Cod sursa (job #237376) | Cod sursa (job #1606230) | Cod sursa (job #2868873)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point
{
double x, y;
};
int indice;
stack <point> stiva;
vector <point> v, res;
bool stanga (point p0, point p1, point p2) // punctul p0 in functie de dreapta determinata de pucntele p1 si p2
{
double det;
det = (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
if (det > 0)
return 1;
return 0;
}
bool cond (point a, point b)
{
if (stanga (v[indice], a, b))
return 1;
return 0;
}
int main ()
{
point x;
int n, i;
f >> n, v.resize (n + 1);
for (i = 1; i <= n; i += 1)
f >> v[i].x >> v[i].y;
indice = 1;
for (i = 2; i <= n; i += 1)
{
if (v[i].y < v[indice].y or (v[i].y == v[indice].y and v[i].x < v[indice].x))
indice = i;
}
swap (v[1], v[indice]);
sort (v.begin () + 2, v.end (), cond);
stiva.push (v[1]), stiva.push (v[2]);
for (i = 3; i <= n; i += 1)
{
x = stiva.top (), stiva.pop ();
while (!stanga (stiva.top (), x, v[i]))
x = stiva.top (), stiva.pop ();
stiva.push (x), stiva.push (v[i]);
}
res.resize (stiva.size () + 1);
g << stiva.size () << '\n', i = 1;
while (!stiva.empty ())
{
res[i] = stiva.top ();
stiva.pop (), i += 1;
}
for (i = res.size () - 1; i >= 1; i -= 1)
{
g << fixed << setprecision (6) << res[i].x << ' ';
g << fixed << setprecision (6) << res[i].y << '\n';
}
return 0;
}