Pagini recente » Cod sursa (job #1733804) | Cod sursa (job #1708305) | Cod sursa (job #415010) | Cod sursa (job #405472) | Cod sursa (job #1076652)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define nmax 120000+5
using namespace std;
ifstream fin("infasuratoare.in");
//ofstream fout("infasuratoare.out");
struct punct
{
double x, y;
punct(double x = 0, double y = 0): x(x), y(y)
{
}
};
double determinant(punct a, punct b, punct c)
{
double d = a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - c.y * a.x - a.y * b.x;
//cout << d << '\n';
return d;
}
bool cmp(punct a, punct b)
{
return a.y < b.y || a.y == b.y && a.x < b.x;
}
punct plan[nmax];
int stiva[nmax];
int n;
int top;
int u[nmax];
int main()
{
int i, cnt;
double det;
fin >> n;
for (i = 1; i <= n; i++)
fin >> plan[i].x >> plan[i].y;
sort(plan + 1, plan + n + 1, cmp);
stiva[++top] = 1;
stiva[++top] = 2;
u[1] = u[2] = 1;
for (i = 3; i <= n; i++)
{
if (!u[i])
{
if (top > 1)
{
det = determinant(plan[stiva[top-1]], plan[stiva[top]], plan[i]);
if (det <= 0)
{
u[stiva[top]] = 0;
top--;
i--;
continue;
}
}
stiva[++top] = i;
u[i] = 1;
}
}
for (i = n; i >= 2; i--)
{
if (!u[i])
{
if (top > 1)
{
det = determinant(plan[stiva[top-1]], plan[stiva[top]], plan[i]);
if (det <= 0)
{
u[stiva[top]] = 0;
top--;
i++;
continue;
}
}
stiva[++top] = i;
u[i] = 1;
}
}
freopen("infasuratoare.out", "w", stdout);
printf("%d\n", top);
//fout << top << '\n';
for (i = 1; i <= top; i++)
{
printf("%llf %llf\n", plan[stiva[i]].x, plan[stiva[i]].y);
//fout << setprecision(8) << plan[stiva[i]].x << ' ' << plan[stiva[i]].y << ' ';
//fout << '\n';
}
//fout << '\n';
return 0;
}