Pagini recente » Cod sursa (job #1131113) | Cod sursa (job #1045733) | Cod sursa (job #410235) | Cod sursa (job #1410474) | Cod sursa (job #2806133)
#include <cstdio>
#include <algorithm>
using namespace std;
FILE* f, * g;
struct name
{
double x, y;
}v[120002];
int sol[120002];
bool viz[120002];
bool how(name A, name B)
{
if (A.x != B.x)
return (A.x < B.x);
return (A.y < B.y);
}
double det(int a, int b, int c)
{
double x1, y1, x2, y2, x3, y3;
x1 = v[a].x;
y1 = v[a].y;
x2 = v[b].x;
y2 = v[b].y;
x3 = v[c].x;
y3 = v[c].y;
double de = x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x1 * y3 - x2 * y1;
return de;
}
int main()
{
f = fopen("infasuratoare.in", "r");
g = fopen("infasuratoare.out", "w");
int n;
fscanf(f, "%d", &n);
for (int i = 1;i <= n;++i)
fscanf(f, "%lf %lf", &v[i].x, &v[i].y);
sort(v + 1, v + n + 1, how);
int ok = 1;
sol[1] = 1;///jonglam cu indicii
sol[2] = 2, viz[2] = 1;
int poz = 3, ss = 2;
while (!viz[1])
{
while (viz[poz])
{
if (poz == n)
ok = -1;
poz += ok;
}
while (ss >= 2 && det(sol[ss - 1], sol[ss], poz) < 0)
viz[sol[ss]] = 0, --ss;
sol[++ss] = poz;
viz[poz] = 1;
}
fprintf(g, "%d\n", ss - 1);
for (int i = 2;i <= ss;++i)
fprintf(g, "%lf %lf\n", v[sol[i]].x, v[sol[i]].y);
fclose(f);
fclose(g);
return 0;
}