Pagini recente » Cod sursa (job #565194) | Borderou de evaluare (job #293485) | Borderou de evaluare (job #565520) | Cod sursa (job #911991) | Cod sursa (job #401864)
Cod sursa(job #401864)
#include <cstdio>
#include <algorithm>
using namespace std;
#define DIM 120005
struct punct
{
double x, y;
} v[DIM], first;
int n;
void swap(int &a, int &b)
{
int aux = a;
a = b;
b = aux;
}
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)
{
return (double)(A.x - v[1].x) * (B.y - v[1].y) > (double)(B.x - v[1].x) * (A.y - v[1].y);
}
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;
int ibun;
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, ibun = i;
else
if (v[i].x == first.x)
if (v[i].y < first.y)
first.y = v[i].y, ibun = i;
}
fclose(f);
swap(v[1], v[ibun]);
for (int i = 1; i <= n; ++i)
printf ("%lf %lf\n", v[i].x, v[i].y);
printf ("\n");
sort(v + 2, v + n + 1, fcmp);
for (int i = 1; i <= n; ++i)
printf ("%lf %lf\n", v[i].x, v[i].y);
graham();
return 0;
}