/*
Infasuratoarea convexa
calc unghi: atan(y/x) * 180 / PI;
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PI 3.14159265
struct punct
{
float x,y;
bool verificat;
};
punct V[10]; int maxPuncte=0;
punct INF[10]; int maxInf=0;
void adauga_punct(punct *vector, int &maxElem,float x,float y);
bool citeste_fisier(char *nume_fisier);
void gaseste_infasuratoare();
punct *gaseste_cel_mai_din_stanga();
punct *gaseste_urmatorul_punct(punct *PCurent, int &zonaC);
bool update_punct_curent_unghi(punct *curent,punct *ptest,punct *&dest, float &unghi, int zona, bool &first);
bool verif_update(punct *sursa,punct *&dest,float &unghi1,float unghi2, int zona,bool &first);
void scrie_fisier(char *nume_fisier);
int main()
{
if ( citeste_fisier("in.txt") == 0 )
return 0;
gaseste_infasuratoare();
scrie_fisier("out.txt");
//system("PAUSE");
return 0;
}
void gaseste_infasuratoare()
{
punct *curent=gaseste_cel_mai_din_stanga();
punct *first= curent;
int zona = 0;
do
{
curent = gaseste_urmatorul_punct(curent,zona);
adauga_punct(INF,maxInf,curent->x,curent->y);
curent->verificat = 1;
}
while ( curent != first );
}
punct *gaseste_urmatorul_punct(punct *PCurent, int &zonaC)
{
int i;
punct *Next=0;
float unghi=0;
bool first=true;
int zonac = 5;
for(i=0;i<maxPuncte;i++)
{
if ( &V[i] == PCurent )
continue;
if ( V[i].verificat == false )
{
if ( V[i].x >= PCurent->x )
{
if ( (V[i].y > PCurent->y) && ( zonaC <= 1 )) // zona 1
{
if ( zonac > 1 )
first = true;
if ( update_punct_curent_unghi(PCurent,&V[i],Next,unghi,1,first) )
zonac = 1;
}
else if ( ( zonac > 1 ) && ( zonaC <= 2) ) // zona 2
{
if ( zonac > 2 )
first = true;
if (update_punct_curent_unghi(PCurent,&V[i],Next,unghi,2,first))
zonac = 2;
}
}
else if ( zonac > 2 )
{
if ( ( V[i].y < PCurent->y) && ( zonaC <= 3 ) ) // zona 3
{
if ( zonac > 3 )
first = true;
if (update_punct_curent_unghi(PCurent,&V[i],Next,unghi,3,first))
zonac = 3;
}
else if ( (zonac > 3) && ( zonaC <= 4) ) // zona 4
{
if (update_punct_curent_unghi(PCurent,&V[i],Next,unghi,4,first))
zonac = 4;
}
}
}
}
zonaC = zonac;
return Next;
}
bool update_punct_curent_unghi(punct *curent,punct *ptest,punct *&dest, float &unghi, int zona,bool &first) // zona 1 = dreapta sus, 2 = dreapta jos, 3 = stanga jos, 4 = stanga sus
{
float unghitmp=0;
float x,y;
if ( zona == 1 )
{
x = abs(ptest->x-curent->x);
y = abs(ptest->y-curent->y);
unghitmp = ( atan(y/x )* 180 / PI );
return verif_update(ptest,dest,unghi,unghitmp,1,first);
}
if ( zona == 2 )
{
x = abs(ptest->x-curent->x);
y = abs(curent->y-ptest->y);
unghitmp = ( atan(y/x )* 180 / PI );
return verif_update(ptest,dest,unghi,unghitmp,2,first);
}
if ( zona == 3 )
{
x = abs(curent->x-ptest->x);
y = abs(curent->y-ptest->y);
unghitmp = ( atan(y/x )* 180 / PI );
return verif_update(ptest,dest,unghi,unghitmp,3,first);
}
if ( zona == 4 )
{
x = abs(ptest->x-curent->x);
y = abs(ptest->y-curent->y);
unghitmp = ( atan(y/x )* 180 / PI );
return verif_update(ptest,dest,unghi,unghitmp,4,first);
}
}
bool verif_update(punct *sursa,punct *&dest,float &unghi1,float unghi2, int zona,bool &first)
{
if ( first || ( zona == 1 && (unghi1 < unghi2)) )
{
dest = sursa;
unghi1 = unghi2;
first = false;
return 1;
}
if ( first || ( zona == 2 && (unghi1 > unghi2) ) )
{
dest = sursa;
unghi1 = unghi2;
first = false;
return 1;
}
if ( first || ( zona == 3 && (unghi1 < unghi2) ) )
{
dest = sursa;
unghi1 = unghi2;
first = false;
return 1;
}
if ( first || ( zona == 4 && ( unghi1 > unghi2 ) ) )
{
dest = sursa;
unghi1 = unghi2;
first = false;
return 1;
}
return 0;
}
punct *gaseste_cel_mai_din_stanga()
{
punct *stg = &V[0];
for(int i=1;i<maxPuncte;i++)
if ( stg->x > V[i].x )
stg = &V[i];
return stg;
}
void scrie_fisier(char *nume_fisier)
{
FILE *f = fopen("out.txt","w");
if ( f == 0 )
return;
fprintf(f,"%d\n",maxInf);
for(int i=0;i<maxInf;i++)
fprintf(f,"%f %f\n",INF[i].x,INF[i].y);
fclose(f);
}
bool citeste_fisier(char *nume_fisier)
{
FILE *f = fopen("in.txt","r");
if ( f == 0 )
return 0;
float x,y;
int maxP=0;
fscanf(f,"%d",&maxP);
if ( maxP == 0 )
{
fclose(f);
return 0;
}
for(int i=0;i<maxP;i++)
{
fscanf(f,"%f %f",&x,&y);
adauga_punct(V,maxPuncte,x,y);
}
fclose(f);
return 1;
}
void adauga_punct(punct *vector, int &maxElem,float x,float y)
{
vector[maxElem].x = x;
vector[maxElem].y = y;
vector[maxElem].verificat = false;
maxElem++;
}