Cod sursa(job #3300730)

Utilizator tudorboscuTudor Boscu tudorboscu Data 18 iunie 2025 18:08:23
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 4.12 kb
#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;
}