Pagini recente » Cod sursa (job #373296) | Cod sursa (job #2073493) | Cod sursa (job #2532005) | Cod sursa (job #1541962) | Cod sursa (job #1507517)
#include <iostream>
#include <fstream>
using namespace std;
ifstream cit("inf.in");
ofstream afi("inf.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;
s[0].x=v[0].x; s[0].y=v[0].y;
while(top1<n)
{ 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++;
if(produs_vectorial(s[top2-2],s[top2-1],s[top2])<1)
top2=top2-2;
else
{m++; top2--; }
}
}
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;
}