Pagini recente » Cod sursa (job #2744709) | Cod sursa (job #2930752) | Cod sursa (job #1613873) | Cod sursa (job #1893461) | Cod sursa (job #2151782)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>
typedef unsigned int uint;
struct Point
{
double x;
double y;
};
void jarvis_march(struct Point *vector, struct Point *keep, uint n, FILE *out);
int orientation(struct Point p, struct Point r, struct Point q);
int main(void)
{
FILE *in = fopen("infasuratoare.in", "r");
FILE *out = fopen("infasuratoare.out", "w");
if(in != NULL && out != NULL)
{
uint n, i = 0;
fscanf(in, "%u%*c", &n);
struct Point *vector = malloc(sizeof(struct Point) * n);
struct Point *keep = malloc(sizeof(struct Point) * n);
if(vector != NULL && keep != NULL)
{
for(; i < n; i++)
{
double a, b;
fscanf(in, "%lf%*c%lf%*c", &a, &b);
struct Point p = {a, b};
vector[i] = p;
}
jarvis_march(vector, keep, n, out);
free(vector);
free(keep);
}
else
{
printf("Error\n");
}
fclose(in);
fclose(out);
}
else
{
printf("file error\n");
}
return 0;
}
int orientation(struct Point p, struct Point q, struct Point r)
{
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if(val == 0)
{
return 0;
}
else if(val > 0)
{
return 2;
}
else
{
return 1;
}
}
void jarvis_march(struct Point *vector, struct Point *keep, uint n, FILE *out)
{
int i = 1;
uint l = 0;
for(; i < n; i++)
{
if(vector[i].x < vector[l].x)
{
l = i;
}
}
uint p = l, q, dx = 0;
do
{
keep[dx++] = vector[p];
q = (p + 1) % n;
uint j = 0;
for(; j < n; j++)
{
if(orientation(vector[p], vector[j], vector[q]) == 2)
{
q = j;
}
}
p = q;
}while(p != l);
i = dx - 1;
for(; i >= 0; i--)
{
fprintf(out, "%.6lf %.6lf\n", keep[i].x, keep[i].y);
}
}