Pagini recente » Cod sursa (job #3171876) | Cod sursa (job #2164850) | Cod sursa (job #40867) | Cod sursa (job #673433) | Cod sursa (job #1507544)
#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;
}