Pagini recente » Cod sursa (job #2593608) | Cod sursa (job #1395225) | Cod sursa (job #714072) | Cod sursa (job #2815116) | Cod sursa (job #2806131)
#include <stdio.h>
#define NMAX 120002
#include <bitset>
#include <algorithm>
using namespace std;
FILE* f, * g;
struct bla
{
double x, y;
}v[NMAX];
int s[NMAX];
bitset <NMAX> viz;
bool how(bla A, bla B)
{
if (A.x == B.x)
return A.y < B.y;
return A.x < B.x;
}
double determinant(bla A, bla B, bla C)
{
double a = A.x, b = A.y, c = B.x, d = B.y, e = C.x, f = C.y;
double delta = a * d + c * f + e * b - d * e - a * f - c * b;
return delta;
}
void make(int n, int& top)
{
int ok = 1, i;
s[1] = 1;
s[2] = 2, viz[2] = 1;
top = 2;
i = 3;
while (!viz[1])
{
while (viz[i])
{
if (i == n) ok = -1;
i += ok;
}
while (determinant(v[s[top - 1]], v[s[top]], v[i]) < 0 && top >= 2)
viz[s[top]] = 0, --top;
///delta=0, punctele sunt coliniare
///delta<0, punctele constituie o orientare in sensul invers acelor de ceasornic
///sens trigonometric
///delta>0, punctele constituie o orientare in sensul acelor de ceasornic
s[++top] = i;
viz[i] = 1;
}
--top;
}
int main()
{
int top;
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);
make(n, top);
fprintf(g, "%d\n", top);
for (int i = 2;i <= top + 1;++i)
fprintf(g, "%lf %lf\n", v[s[i]].x, v[s[i]].y);
fclose(f);
fclose(g);
return 0;
}