Pagini recente » Cod sursa (job #1283835) | Cod sursa (job #922944) | Cod sursa (job #1160736) | Cod sursa (job #196295) | Cod sursa (job #1076695)
#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;
float minx = 1 << 30;
fin >> n;
for (i = 1; i <= n; i++)
{
fin >> plan[i].x >> plan[i].y;
if (plan[i].x < minx)
minx = plan[i].x;
}
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';
/*int poz = 0;
for (i = 1; i <= top; i++)
if (plan[stiva[i]].x == minx)
poz = i;
*/
for (i = 1; i <= top; i++)
{
//int actual = i;//(i + poz - 2) % top + 1;
//printf("%llf %llf\n", plan[stiva[actual]].x, plan[stiva[actual]].y);
fout << setprecision(8) << plan[stiva[i]].x << ' ' << plan[stiva[i]].y << ' ';
fout << '\n';
}
fout << '\n';
return 0;
}