Pagini recente » Cod sursa (job #679687) | Cod sursa (job #1122105) | Cod sursa (job #600578) | Cod sursa (job #3139172) | Cod sursa (job #2806132)
#include <fstream>
#define N 120002
#include <algorithm>
#include <bitset>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
bitset <N> viz;
int who[N];
struct bla
{
long double x, y;
}v[N];
bool cmp(bla A, bla B)
{
if (A.x != B.x) return A.x < B.x;
return A.y < B.y;
}
long double det(int a, int b, int c)
{
long double x1 = v[a].x, x2 = v[b].x, x3 = v[c].x, y1 = v[a].y, y2 = v[b].y, y3 = v[c].y;
long double d;
d = (x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x1 * y3 - x2 * y1);
return d;
}
int main()
{
int n, nr = 1, i, ss = 2;
f >> n;
for (int i = 1;i <= n;++i) f >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
who[1] = 1;
who[2] = 2, viz[2] = 1;
i = 3;
while (!viz[1])
{
while (viz[i])
{
if (i == n) nr = -1;
i += nr;
}
while (ss >= 2 && det(who[ss - 1], who[ss], i) < 0)
viz[who[ss]] = 0, --ss;
who[++ss] = i;
viz[who[ss]] = 1;
}
g << ss - 1 << '\n';
for (int i = 2;i <= ss;++i)
{
g << fixed << setprecision(15) << v[who[i]].x << ' ';
g << fixed << setprecision(15) << v[who[i]].y << '\n';
}
f.close();
g.close();
return 0;
}