Pagini recente » Cod sursa (job #1016908) | Cod sursa (job #508305) | Cod sursa (job #257208) | Cod sursa (job #218862) | Cod sursa (job #401477)
Cod sursa(job #401477)
#include <cstdio>
#include <algorithm>
using namespace std;
#define DIM 120005
struct punct
{
double x, y;
} v[DIM], first;
int n;
double dist(punct A, punct B)
{
return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
int directie(punct A, punct B, punct C)
{
double d = (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y);
if (d == 0) //coliniare
return 0;
if (d < 0) //dreapta
return -1;
//stanga
return 1;
printf ("WTF?\n");
}
int fcmp(punct A, punct B)
{
int d = directie(v[1], A, B);
if (d > 0)
return 1;
else
if (d < 0)
return -1;
else
return dist(v[1], A) < dist(v[1], B);
}
void graham()
{
int S[DIM], top = 0;
S[++top] = 1;
S[++top] = 2;
for (int i = 3; i <= n; ++i)
{
while (directie(v[S[top - 1]], v[S[top]], v[i]) <= 0 && top >= 2 ) //stanga
--top;
S[++top] = i;
}
FILE *f = fopen("infasuratoare.out", "w");
fprintf (f, "%d\n", top);
for (int i = 1; i <= top; ++i)
fprintf(f, "%lf %lf\n", v[S[i]].x, v[S[i]].y);
}
int main()
{
FILE *f = fopen("infasuratoare.in", "r");
fscanf(f, "%d", &n);
first.x = 1<<30, first.y = 1<<30;
for (int i = 1; i <= n; ++i)
{
fscanf(f, "%lf%lf", &v[i].x, &v[i].y);
if (v[i].x < first.x)
first.x = v[i].x, first.y = v[i].y;
else
if (v[i].x == first.x)
if (v[i].y < first.y)
first.y = v[i].y;
}
fclose(f);
sort(v + 2, v + n + 1, fcmp);
graham();
return 0;
}