Pagini recente » Cod sursa (job #2297794) | Cod sursa (job #467683) | Cod sursa (job #854762) | Cod sursa (job #2802104) | Cod sursa (job #1529106)
#include <fstream>
#include <iomanip>
#include <algorithm>
struct pair
{
double x, y;
friend bool operator<(const pair& lhs, const pair& rhs)
{
return lhs.x < rhs.x || (!(rhs.x < lhs.x) && lhs.y < rhs.y);
}
};
int n, top, pos, s[120010];
pair v[120010];
std::fstream in, out;
double det(pair a, pair b, pair c)
{
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
bool cmp(pair a, pair b)
{
return (det(v[1], a, b) < 0);
}
int main(int argc, char *argv[])
{
in.open("infasuratoare.in", std::fstream::in);
out.open("infasuratoare.out", std::fstream::out);
in >> n;
pos = 1;
for (int i = 1; i <= n; ++i)
{
in >> v[i].x >> v[i].y;
if (v[i] < v[pos]) pos = i;
}
std::swap(v[1], v[pos]);
std::sort(v + 2, v + n + 1, cmp);
s[++top] = 1;
for (int i = 2; i <= n; ++i)
{
while (top > 1 && det(v[s[top - 1]], v[s[top]], v[i]) > 0) --top;
s[++top] = i;
}
out << top << "\n";
while (top)
{
out << std::fixed << std::setprecision(6) << v[s[top]].x << ' ' << v[s[top]].y << "\n";
--top;
}
return 0;
}
// http://informaticasite.ro/backtracking/352-permutari-iterativ.html