Cod sursa(job #2151782)

Utilizator arcoC. Nicolae arco Data 4 martie 2018 21:41:31
Problema Infasuratoare convexa Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.77 kb
#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);
	}
}