Pagini recente » Cod sursa (job #3292551) | Cod sursa (job #3287809) | Cod sursa (job #378883) | Cod sursa (job #3293815) | Cod sursa (job #3292552)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define double long double
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int Nmax = 120005;
struct punct
{
double x, y;
}p[Nmax];
bool cmp(punct a, punct b)
{
if (a.y != b.y)
return a.y < b.y;
return a.x < b.x;
}
int semn(punct a, punct b, punct c)//imi da semnul determinantului
{
double det = a.x * b.y - b.y * c.x + b.x * c.y - c.y * a.x + c.x * a.y - a.y * b.x;
if (det > 0) return 1;
if (det < 0) return -1;
return 0;
}
int ans[Nmax];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> p[i].x >> p[i].y;
sort(p + 1, p + n + 1, cmp);
ans[++ans[0]] = 1;
ans[++ans[0]] = 2;
for (int i = 3; i <= n; i++)
{
int sz = ans[0];
while (sz > 1 && semn(p[ans[sz - 1]], p[ans[sz]], p[i]) == -1)
{
ans[0]--;
sz = ans[0];
}
ans[++ans[0]] = i;
}
for (int i = n - 1; i >= 1; i--)//n e ult punct pus
{
int sz = ans[0];
while (sz > 1 && semn(p[ans[sz - 1]], p[ans[sz]], p[i]) == -1)
{
ans[0]--;
sz = ans[0];
}
ans[++ans[0]] = i;
}
cout << ans[0] - 1 << '\n';
for (int i = 1; i < ans[0]; i++)//ult punct e acelasi cu primul
cout << fixed << setprecision(12) << p[ans[i]].x << " " << p[ans[i]].y << '\n';
}