Pagini recente » Cod sursa (job #2163689) | Cod sursa (job #3029984) | Cod sursa (job #2282200) | Cod sursa (job #370267) | Cod sursa (job #1529090)
#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], aux;
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[0], 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;
}