Pagini recente » Cod sursa (job #2552832) | Cod sursa (job #1010865) | Cod sursa (job #1480486) | Cod sursa (job #2300486) | Cod sursa (job #3300730)
#include <stdio.h>
#include <stdlib.h>
#define MAX 1200012
//din ce tin minte la curs trebuie sa lucram cu unghiul polar al punctelor (cel pe cadrane raportat la origine)
//ne vom folosi de determinant pt a vedea cum este unghiul
typedef struct{
double x;
double y;
}PUNCT;
PUNCT origine;
PUNCT puncte[MAX];
int size_puncte = 0;
// lucram cu o stiva pt indicii punctelor din infasuratoare
int stack[MAX];
int top = -1;
void push(int x){
if (top == MAX - 1){
fprintf(stderr, "stiva full.\n");
}
else{
top++;
stack[top] = x;
}
}
int pop(){
if (top == -1){
fprintf(stderr, "stiva goala.\n");
return -1;
}
else{
int x = stack[top];
top--;
return x;
}
}
int peek(){
if (top == -1){
fprintf(stderr, "stiva goala.\n");
return -1;
}
else{
return stack[top];
}
}
// am scris repede functiile standard de stiva just in case.
//e determinant de 2x2 din care scadem originea (pe coloana cu x scaden originea.x si pe cealalta
// coloana la fel cu originea.y)
double determinant(PUNCT a, PUNCT b){
return (a.x - origine.x) * (b.y - origine.y) - (a.y - origine.y) * (b.x - origine.x);
}
int cmp_for_qsort(const void *a, const void *b)
{
PUNCT *p1 = (PUNCT *)a;
PUNCT *p2 = (PUNCT *)b;
double det = determinant(*p1, *p2);
if (det > 0){
return -1;
}
if (det < 0){
return 1;
}
//daca e 0 determinantul il punem pe ala de mai aproape
double dist1 = (p1->x - origine.x) * (p1->x - origine.x) + (p1->y - origine.y) * (p1->y - origine.y);
double dist2 = (p2->x - origine.x) * (p2->x - origine.x) + (p2->y - origine.y) * (p2->y - origine.y);
if (dist1 < dist2){
return -1;
}
return 1;
}
void get_origin() //punem punctu cel mai de jos si cel mai din stanga
{
int pos = 0;
for(int i = 1; i < size_puncte; i++){
if (puncte[i].y < puncte[pos].y){
pos = i;
}
if (puncte[i].y == puncte[pos].y && puncte[i].x < puncte[pos].x){
pos = i;
}
}
//schimbam punctul gasit cu primul ca sa fie originea prima din array ca sa putem sorta
//in functie de unghiul polar in raport cu originea gasita
PUNCT aux = puncte[0];
puncte[0] = puncte[pos];
puncte[pos] = aux;
origine = puncte[0];
printf("Originea: %lf %lf\n", origine.x, origine.y);
}
void get_origin_and_sort()
{
get_origin();
qsort(puncte + 1, size_puncte - 1, sizeof(PUNCT), cmp_for_qsort);
}
void solve_stack()
{
get_origin_and_sort(); //avem originea si o avem pusa pe prima pozitie
push(0); //punem originea in stack
for(int i = 1; i < size_puncte; i++){
while (top >= 1){ //adica sa avem cel putin 2 elemente in stiva ca sa nu verificam si originea
int last = pop(); //din varf
int before_last = peek(); //ala de sub el
double det = (puncte[last].x - puncte[before_last].x) * (puncte[i].y - puncte[before_last].y) - (puncte[last].y - puncte[before_last].y) * (puncte[i].x - puncte[before_last].x);
// la fel ca si cu originea, acum vrem sa vedem daca viram la stanga sau nu
if (det > 0){
//daca viram la stanga il punem inapoi
//ca vrem sa ramana convex si sa includem punctele
push(last);
break;
}
}
push(i); //punem punctu in stiva;
}
}
int main(void)
{
FILE *fin = NULL;
FILE *fout = NULL;
fin = fopen("infasuratoare.in", "r");
fout = fopen("infasuratoare.out", "w");
// scanf("%d", &size_puncte);
fscanf(fin, "%d", &size_puncte);
for(int i = 0; i < size_puncte; i++){
fscanf(fin, "%lf %lf", &puncte[i].x, &puncte[i].y);
// scanf("%lf %lf", &puncte[i].x, &puncte[i].y);
}
solve_stack();
fprintf(fout, "%d\n", top + 1);
// printf("%d\n", top + 1);
for(int i = 0; i <= top; i++){
fprintf(fout, "%lf %lf\n", puncte[stack[i]].x, puncte[stack[i]].y );
// printf("%lf %lf\n", puncte[stack[i]].x, puncte[stack[i]].y );
}
fclose(fin);
fclose(fout);
return 0;
}