Cod sursa(job #1507544)

Utilizator paul.xhFMI Porohniuc Paul-Stefan paul.xh Data 21 octombrie 2015 18:51:51
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.39 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream cit("infasuratoare.in");
ofstream afi("infasuratoare.out");

struct punct
{ float x,y;
};

void alege_punct_start(punct v[100], int n)
{
   int i,poz=0;
   punct init;
   init.x=v[0].x; init.y=v[0].y;
   for(i=1;i<n;i++)
     if(v[i].x<init.x)
         {init.x=v[i].x; init.y=v[i].y; poz=i;}
       else
        if(v[i].x==init.x && v[i].y<init.y)
             {init.x=v[i].x; init.y=v[i].y; poz=i;}
   v[poz].x=v[0].x; v[poz].y=v[0].y; v[0].x=init.x; v[0].y=init.y;
}

float panta(punct A, punct B)
{ if((B.x-A.x)==0) return 0; else return (B.y-A.y)/(B.x-A.x); }

float produs_scalar(punct A, punct B)
{ return ((A.x*B.x)+(A.y*B.y));}

void sortare_puncte_panta(punct v[100], int n)
{
  int i,j;
  punct aux;
  for(i=1;i<n;i++)
     for(j=i+1;j<n;j++)
        if(produs_scalar(v[0],v[i])>produs_scalar(v[0],v[j]))
          { aux.x=v[i].x; aux.y=v[i].y;
            v[i].x=v[j].x; v[i].y=v[j].y;
            v[j].x=aux.x; v[j].y=aux.y;
          }
}

float produs_vectorial(punct A, punct B, punct C)
{ return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x); }

void infasuratoare_convexa(punct v[100], punct s[100], int n, int &m)
{
   m=1;
   int top1=1,top2=1,ok=0;
   s[0].x=v[0].x; s[0].y=v[0].y;
   while(top1<n-1)
   { s[top2].x=v[top1].x; s[top2].y=v[top1].y;
     top1++; top2++;
     s[top2].x=v[top1].x; s[top2].y=v[top1].y;
     top2++;
     //afi<<"am calculat "<<s[top2-3].x<<","<<s[top2-3].y<< " si "<<s[top2-2].x<<","<<s[top2-2].y<<" si "<<s[top2-1].x<<","<<s[top2-1].y<<" si da "<<produs_vectorial(s[top2-3],s[top2-2],s[top2-1])<<" si top2 e "<<top2<<endl;
     if(produs_vectorial(s[top2-3],s[top2-2],s[top2-1])<1)
        {top2=top2-2; ok=0; }
       else
        {m++; top2--; ok=1; }

   }
   if(ok==1) m++;
}

int main()
{
  int n,m,i;
  cit>>n;

  if(n==2) {afi<<"Infasuratoarea convexa este alcatuita din segmentul realizat de cele 2 puncte introduse."<<endl; return 0;}
  if(n<=1) {afi<<"Sunt prea putine puncte pentru a realiza infasuratoarea convexa."<<endl; return 0;}

  punct pct[100],inf[100];
  for(i=0;i<n;i++)
     cit>>pct[i].x>>pct[i].y;

     alege_punct_start(pct,n);
     sortare_puncte_panta(pct,n);
     infasuratoare_convexa(pct,inf,n,m);

   
     afi<<m<<endl;
       for(i=0;i<m;i++)
          afi<<inf[i].x<<" "<<inf[i].y<<endl;

    return 0;
}