Cod sursa(job #1525694)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 15 noiembrie 2015 14:02:52
Problema Infasuratoare convexa Scor 50
Compilator c Status done
Runda Arhiva educationala Marime 2.07 kb
#include <stdio.h>
#include <stdlib.h>

struct punct{
  double x, y;
}v[120000];
int conv[120000];
int s[120000], p[120000];

int determinant(int p1, int p2, int p3){
  return v[p1].x*v[p2].y+v[p2].x*v[p3].y+v[p3].x*v[p1].y-v[p3].x*v[p2].y-v[p1].x*v[p3].y-v[p2].x*v[p1].y;
}

int sens(int vf){
  if(determinant(p[s[vf-2]],p[s[vf-1]],p[s[vf]])<0)
    return -1;
  return 1;
}

struct dreapta{
  double a, b, c;
};

int comp(struct punct p1, struct punct p2){
  if(p1.x<p2.x)
    return 1;
  else if(p1.x>p2.x)
    return 0;
  else if(p1.y<p2.y)
    return 1;
  else
    return 0;
}

void myqsort( int begin, int end ) {
  int aux, b = begin, e = end;
  struct punct  pivot = v[p[begin + rand() % (end - begin + 1)]];
  while ( b <= e ) {
    while ( comp(v[p[b]],pivot) ) b++;
    while ( comp(pivot,v[p[e]]) ) e--;
    if ( b <= e ) {
      aux = p[b]; p[b] = p[e]; p[e] = aux;
      b++; e--;
    }
  }
  if ( begin < e ) myqsort( begin, e );
  if ( b < end ) myqsort( b, end );
}

int main()
{
  int n, i, poz, vf;
  FILE *fi=fopen("infasuratoare.in", "r"), *fo=fopen("infasuratoare.out", "w");
  fscanf(fi, "%d", &n);
  //citire
  for(i=0;i<n;i++){
    fscanf(fi, "%lf%lf", &v[i].x, &v[i].y);
    p[i]=i;
  }
  myqsort(0,n-1);
  /*for(u=n-1;u>0;u--){
    max=v[p[u]].x;
    poz=u;
    for(i=0;i<u;i++)
      if(v[p[i]].x>max){
        max=v[p[i]].x;
        poz=i;
      }
    aux=p[u];
    p[u]=p[poz];
    p[poz]=aux;
  }*/
  s[0]=0;
  s[1]=1;
  vf=1;
  for(i=2;i<n;i++){
    vf++;
    s[vf]=i;
    while(vf>1 && sens(vf)==1){
      s[vf-1]=s[vf];
      vf--;
    }
  }
  poz=0;
  for(i=vf;i>=0;i--){
    conv[poz]=p[s[i]];
    poz++;
  }
  s[0]=n-1;
  s[1]=n-2;
  vf=1;
  for(i=n-3;i>=0;i--){
    vf++;
    s[vf]=i;
    while(vf>1 && sens(vf)==1){
      s[vf-1]=s[vf];
      vf--;
    }
  }
  for(i=vf-1;i>0;i--){
    conv[poz]=p[s[i]];
    poz++;
  }
  fprintf(fo, "%d", poz);
  for(i=0;i<poz;i++)
    fprintf(fo, "\n%lf %lf", v[conv[i]].x, v[conv[i]].y);
  fclose(fi);
  fclose(fo);
  return 0;
}