Cod sursa(job #3300626)

Utilizator tudor-cristian.saftescuSaftescu Tudor Cristian tudor-cristian.saftescu Data 18 iunie 2025 01:48:59
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 3.18 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAXN 120005 //putin mai mare ca N-ul maxim 

typedef struct{
    double x, y;
}Point;

Point p[MAXN];//vectorul de puncte
int st[MAXN];
int n,sz;//n e numarul de puncte date de problema si sz e numarul de puncte pe care le folosim

double orientation(Point a, Point b, Point c)//calculeaza determinantul pentru a determina orientarea(practic unghiul)
{
    return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}

double manhattan(Point a, Point b)//distanta Manhattan, e mai simplu ca cea euclidiana
{
    return fabs(a.x-b.x)+fabs(a.y-b.y);
}

int cmp(const void* A, const void* B)//functie de comparare pt qsort, compara unghiurile celor 2 puncte cu punctul de start
{
    Point a=*(Point*)A;
    Point b=*(Point*)B;
    double orient=orientation(p[0],a,b);
    if (fabs(orient)<1e-12) 
    {
        if (a.x!=b.x) 
            return (a.x<b.x)?-1:1;
        return (a.y<b.y)?-1:1;
    }
    return (orient>0)?-1:1;
}

void find_lowest()//functia care gaseste cel mai din stanga punct, in caz de egalitate a 2 x-uri ia y-ul mai mic 
{
    int ind=0;
    for (int i=1;i<n;i++)
    {
        if (p[i].x<p[ind].x || (p[i].x==p[ind].x && p[i].y<p[ind].y)) 
        {
            ind=i;
        }
    }
    Point tmp=p[0];
    p[0]=p[ind];//schimba primul punct din lista cu cel gasit ca cel mai in stanga-jos
    p[ind]=tmp;
}

void sort_points()//sorteaza punctele in mod eficient 
{
    qsort(p+1,n-1,sizeof(Point),cmp);
}

void convex_hull()//folosim algoritmul graham scan
{
    sz=0;
    for(int i=0; i<n;i++) 
    {
        while (sz>=2 && orientation(p[st[sz-2]],p[st[sz-1]],p[i])<=1e-12)
            sz--;
        st[sz++]=i;
    }
}

int main(void) 
{
    FILE *fin=fopen("infasuratoare.in", "r");
    FILE *fout=fopen("infasuratoare.out", "w");
    
     if(fin==NULL)//verificam deschiderea fisierelor
    {
        perror("Eroare la deschiderea fisierului de citire.\n");
        exit(1);
    }
    if(fout==NULL)
    {
        perror("Eroare la deschiderea fisierului de scriere.\n");
        exit(1);
    }
    
    if(fscanf(fin, "%d", &n)!=1)//citim numarul n de puncte
    {
        perror("Eroare la citirea din fisier.\n");
        exit(1);
    }
    
    for (int i=0;i<n;i++) //apoi citim cele n puncte
    {
        if(fscanf(fin, "%lf %lf", &p[i].x, &p[i].y)!=2)
            {
                perror("Eroare la citirea din fisier.\n");
                exit(1);
            }
    }

    find_lowest();//gasim cel mai din stanga-jos punct(startul)
    sort_points();
    convex_hull();//cautam ce puncte ne trebuie si le salvam in vector dar si schimbam sz-ul de fiecare data cand gasim un punct
    
    fprintf(fout,"%d\n",sz);//scriem cate laturi si care laturi sunt incluse
    for (int i=0;i<sz;i++) 
    {
        fprintf(fout,"%.12lf %.12lf\n",p[st[i]].x,p[st[i]].y);
    }
    
    if(fclose(fin)!=0)//verificam inchiderea fisierelor
    {
        perror("Eroare inchidere fisier citire.\n");
        exit(1);
    }
    if(fclose(fout)!=0)
    {
        perror("Eroare inchidere fisier scriere.\n");
        exit(1);
    }
    
    return 0;
}