Pagini recente » Cod sursa (job #436270) | Infoarena Monthly 2014 - Clasament | Cod sursa (job #91593) | Cod sursa (job #2630774) | Cod sursa (job #3301022)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#define MAX 120001
typedef struct
{
float x, y;
}Coord;
long int N, stanga = 0;
Coord puncte[MAX], infasuratoare[MAX];
typedef Coord Element_t;
typedef struct
{
Element_t st[MAX];
size_t cap;
size_t vf;
}Stack_t;
Stack_t stack;
typedef enum ErrorCode
{
PUSH_OK, STACK_EMPTY, STACK_FULL
}EC_t;
void interpretare_eroare(EC_t eroare)
{
switch(eroare)
{
case 0:
{
printf("Elementul a ajuns in stiva cu succes!\n");
break;
}
case 1:
{
printf("Stiva este goala!\n");
break;
}
case 2:
{
printf("Stiva este plina!\n");
break;
}
default:
break;
}
eroare = 3;
}
void push(Stack_t *stiva, Element_t nou)
{
if(stiva->vf == stiva->cap - 1)
{
EC_t eroare = STACK_FULL;
interpretare_eroare(eroare);
return;
}
else
{
(stiva->vf)++;
stiva->st[stiva->vf] = nou;
}
}
Element_t pop(Stack_t *stiva)
{
Element_t data;
if(stiva->vf == -1)
{
EC_t eroare = STACK_EMPTY;
interpretare_eroare(eroare);
return (Coord){0, 0};
}
else
{
data = stiva->st[stiva->vf];
(stiva->vf)--;
return data;
}
}
float cross(Coord p1, Coord p2, Coord p3)
{
return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}
int compare(const void* p1, const void* p2)
{
Coord punct1 = *(Coord*)p1, punct2 = *(Coord*)p2;
float val = cross(puncte[0], punct1, punct2);
if (val > 0)
return -1;
if (val < 0)
return 1;
float d1 = (punct1.x - puncte[0].x)*(punct1.x - puncte[0].x) + (punct1.y - puncte[0].y)*(punct1.y - puncte[0].y);
float d2 = (punct2.x - puncte[0].x)*(punct2.x - puncte[0].x) + (punct2.y - puncte[0].y)*(punct2.y - puncte[0].y);
if(d1 < d2)
return -1;
else
return 1;
}
void citire(FILE *input)
{
fscanf(input, "%ld", &N);
if(N < 3)
{
printf("Prea putine puncte.");
exit(-1);
}
for(int i = 0; i < N; i++)
{
fscanf(input, "%f %f", &puncte[i].x, &puncte[i].y);
if(puncte[i].x < puncte[stanga].x)
stanga = i;
else if(puncte[i].x == puncte[stanga].x)
if(puncte[i].y < puncte[stanga].y)
stanga = i;
}
Coord aux;
aux = puncte[0];
puncte[0] = puncte[stanga];
puncte[stanga] = aux;
qsort(puncte + 1, N - 1, sizeof(puncte[0]), compare);
}
void infasurare()
{
push(&stack, puncte[0]);
push(&stack, puncte[1]);
for(int i = 2; i < N; i++)
{
while(stack.vf >= 1 && cross(stack.st[stack.vf - 1], stack.st[stack.vf], puncte[i]) <= 0)
pop(&stack);
push(&stack, puncte[i]);
}
}
void afisare(FILE *output)
{
fprintf(output, "%ld\n", stack.vf + 1);
float orientare = 0;
for(int i = 0; i <= stack.vf; i++)
orientare += cross(stack.st[i], stack.st[i+1], stack.st[0]);
if (orientare < 0)
{
for(int i = 0; i <= stack.vf/2; i++)
{
Coord aux = stack.st[i];
stack.st[i] = stack.st[stack.vf - i];
stack.st[stack.vf - i] = aux;
}
}
for(int i = 1; i <= stack.vf; i++)
fprintf(output, "%.12f %.12f\n", stack.st[i].x, stack.st[i].y);
fprintf(output, "%.12f %.12f\n", stack.st[0].x, stack.st[0].y);
}
int main()
{
FILE *input, *output;
if((input = fopen("infasuratoare.in", "r")) == NULL)
{
perror("Eroare la deschidere fisier intrare.");
exit(-1);
}
citire(input);
stack.cap = MAX;
stack.vf = -1;
infasurare();
if((output = fopen("infasuratoare.out", "w")) == NULL)
{
perror("Eroare la deschidere fisier iesire.");
exit(-1);
}
afisare(output);
if(fclose(input) == -1)
{
perror("Eroare la inchidere fisier intrare.");
exit(-1);
}
if(fclose(output) == -1)
{
perror("Eroare la inchidere fisier iesire.");
exit(-1);
}
return 0;
}