Cod sursa(job #639727)

Utilizator mr.johnFMI - Laceanu Ionut-Adrian mr.john Data 23 noiembrie 2011 21:17:51
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.37 kb
#include <stdio.h>
#include <fstream>

using namespace std;
struct punct{double x,y;};
int varf,crt,n;
punct v[120001],stiva[120001],prim;
FILE *f=fopen("infasuratoare.in","r");

inline double panta(punct a){return (a.y-prim.y)/(a.x-prim.x);};
inline bool maijos(punct a, punct b){if (panta(a)<panta(b)) return 1; else return 0;} 
inline double determinant(punct unu, punct doi, punct trei){
  return (unu.x*doi.y+doi.x*trei.y+trei.x*unu.y-unu.x*trei.y-doi.x*unu.y-trei.x*doi.y);}

void adaugare(){
  if (determinant(stiva[varf-1],stiva[varf],v[crt])<0){
    varf--;
    adaugare();
  }
  else{
    stiva[++varf]=v[crt++];
    if (crt>n) return;
    adaugare();
  }
}
    

void merge(int min, int med, int max)
{
  int i=min;
  int j=med+1;
  int k=min;
  punct b[120001];
  while((i<=med) && (j<=max))
  {
    if (maijos(v[i],v[j]))
    {
      b[k++]=v[i++];
    }
    else
    {
      b[k++]=v[j++];
    }
  }
  if (j>max)
    while (i<=med)
    {
      b[k]=v[i];
      i++;
      k++;
    }
  else
    while (j<=max)
    {
      b[k]=v[j];
      j++;
      k++;
    }
  for (int i=min;i<=max;i++)
    v[i]=b[i];  
}

void merge_sort(int minimum,int maximum)
{
  if (minimum<maximum)
  {
    int medium=(minimum+maximum)/2;
    merge_sort(minimum,medium);
    merge_sort(medium+1,maximum);
    merge(minimum,medium,maximum);
  }
}

void citire(){
  int unde=1;
  punct aux;
  fscanf(f,"%d ",&n);
  fscanf(f,"%Lf %Lf ",&v[1].x,&v[1].y);
  prim=v[1];
  for (int i=2;i<=n;i++){
    fscanf(f,"%Lf %Lf ",&v[i].x,&v[i].y);
    if (v[i].x<prim.x){prim=v[i];unde=i;}
    if (v[i].x==prim.x && v[i].y<prim.y){prim=v[i];unde=i;}
  }
//  system("PAUSE");
//  for (int j=1;j<=n;j++)
//    printf("%.6Lf %.6Lf \n",v[j].x,v[j].y);
//  printf("%.6Lf %.6Lf \n",prim.x,prim.y);  
//    system("PAUSE");
  aux=v[1]; v[1]=prim; v[unde]=aux;
  fclose(f);
}
    

int main()
{
  freopen("infasuratoare.out","w",stdout);
  citire();
  merge_sort(2,n);
  stiva[1]=v[1];
  stiva[2]=v[2];
  varf=2;
  crt=3;
  adaugare();
  ofstream fout("infasuratoare.out");
  fout.setf(ios::floatfield);
  fout.precision(12);
  fout<<fixed;
  fout<<varf<<"\n";  
//  printf("%d\n",varf);
  for (int i=1;i<=varf;i++)
    fout<<stiva[i].x<<" "<<stiva[i].y<<"\n";
//    printf("%.6Lf %.6Lf\n",stiva[i].x,stiva[i].y);
  fout.close();
  return 0;
}