Cod sursa(job #3299906)

Utilizator rares-razvan.boldeaRares-Razvan Boldea rares-razvan.boldea Data 11 iunie 2025 17:58:58
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 3.27 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define pi 3.14159265
typedef struct
{
  double x,y;
}Punct;
Punct start;
typedef struct
{
  double x,y;
}Vector;
struct Node
{
  Punct *p;
  struct Node *ant;
};
typedef struct
{
  int size;
  struct Node *head;
}Stack;
Stack *createStack()
{
  Stack *s=malloc(sizeof(Stack));
  s->size=0;
  s->head=NULL;
  return s;
}
void pushStack(Stack *s,Punct *p)
{
  struct Node *n=malloc(sizeof(struct Node));
  n->p=p;
  n->ant=s->head;
  s->head=n;
  s->size++;
}
void popStack(Stack *s)
{
  if(s->head!=NULL)
  {
    struct Node *aux=s->head;
    s->head=s->head->ant;
    free(aux);
    s->size--;
  }
}
void deleteStack(Stack *s)
{
  while(s->head!=NULL)
    popStack(s);
  free(s);
}
void reverseStack(Stack **s)
{
  Stack *aux=*s;
  *s=createStack();
  while(aux->head!=NULL)
  {
    pushStack(*s,aux->head->p);
    popStack(aux);
  }
  free(aux);
}
void printStack(Stack *s,FILE *out)
{
  struct Node *n=s->head;
  while(n)
  {
    fprintf(out,"%lf %lf\n",n->p->x,n->p->y);
    n=n->ant;
  }
}
int isSmaller(Punct *a,Punct *b)
{
  if(a->y > b->y)
    return 0;
  if((a->y < b->y) || (a->x < b->x))
    return 1;
  return 0;
}
Vector createVector(Punct *a,Punct *b)
{
  Vector v;
  v.x=b->x - a->x;
  v.y=b->y - a->y;
  return v;
}
double magnitude(Vector v)
{
  return sqrt(v.x*v.x + v.y*v.y);
}
double dotProd(Vector a,Vector b)
{
  return a.x*b.x + a.y*b.y;
}
double cosVector(Vector a,Vector b)
{
  return dotProd(a,b)/(magnitude(a)*magnitude(b));
}
int compar(const void *a,const void *b)
{
  Punct *punct_a=(Punct *)a;
  Punct *punct_b=(Punct *)b;
  if(punct_a->x==start.x && punct_a->y==start.y)
    return -1;
  if(punct_b->x==start.x && punct_b->y==start.y)
    return 1;

  Vector va=createVector(&start,punct_a);
  Vector vb=createVector(&start,punct_b);
  Vector i= {1,0};
  double cos_va=cosVector(va,i);
  double cos_vb=cosVector(vb,i);
  
  if(cos_va>cos_vb)
    return -1;
  if(cos_va<cos_vb)
    return 1;
  return 0;
}
Vector getLeftDirection(Vector v)
{
  int sign= v.y>=0?1:-1;
  Vector i= {1,0};
  double radial_angle=sign*acos(cosVector(v,i));
  double leftDirection_angle=pi/2+radial_angle;
  Vector leftDirection= {cos(leftDirection_angle),sin(leftDirection_angle)};
  return leftDirection;
}
int leftTurn(Vector v0,Vector v1)
{
  Vector n=getLeftDirection(v0);
  return dotProd(n,v1)>0;
}
void infasuratoare(Punct *p,int n,FILE *out)
{
  Vector anterior,curent;
  Stack *s=createStack();
  qsort(p,n,sizeof(Punct),compar);
  
  anterior=createVector(p,p+1);
  pushStack(s,p);
  pushStack(s,p+1);

  for(int i=2;i<n;i++)
  {
    curent=createVector(s->head->p,p+i);
    while(!leftTurn(anterior,curent))
    {
      popStack(s);
      curent=createVector(s->head->p,p+i);
      anterior=createVector(s->head->ant->p,s->head->p);
    }
    pushStack(s,p+i);
    anterior=curent;
  }
  fprintf(out,"%d\n",s->size);
  reverseStack(&s);
  printStack(s,out);
  deleteStack(s);
}
int main()
{
  int n;
  Punct p[120000];
  FILE *in=fopen("infasuratoare.in","r"),*out=fopen("infasuratoare.out","w");
  fscanf(in,"%d",&n);
  
  fscanf(in,"%lf %lf",&(p[0].x),&(p[0].y));
  start=p[0];
  for(int i=1;i<n;i++)
  {
    fscanf(in,"%lf %lf",&(p[i].x),&(p[i].y));
    if(isSmaller(p+i,&start))
      start=p[i];
  }
  
  infasuratoare(p,n,out);
  fclose(in);
  fclose(out);
  return 0;
}