/*
Infasuratoarea convexa
calc unghi: atan(y/x) * 180 / PI;
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PI 3.14159265
struct punct
{
double x,y;
bool verificat;
};
punct V[120000]; int maxPuncte=0;
punct INF[120000]; int maxInf=0;
void adauga_punct(punct *vector, int &maxElem,double x,double 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, double &unghi, int zona, bool &first);
bool verif_update(punct *sursa,punct *&dest,double &unghi1,double unghi2, int zona,bool &first);
void scrie_fisier(char *nume_fisier);
int main()
{
if ( citeste_fisier("infasuratoare.in") == 0 )
return 0;
gaseste_infasuratoare();
scrie_fisier("infasuratoare.out");
//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);
if ( curent == 0 )
break;
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;
double 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, double &unghi, int zona,bool &first) // zona 1 = dreapta sus, 2 = dreapta jos, 3 = stanga jos, 4 = stanga sus
{
double unghitmp=0;
double x,y;
if ( zona == 1 )
{
x = abs(ptest->x-curent->x);
y = abs(ptest->y-curent->y);
}
if ( zona == 2 )
{
x = abs(ptest->x-curent->x);
y = abs(curent->y-ptest->y);
}
if ( zona == 3 )
{
x = abs(curent->x-ptest->x);
y = abs(curent->y-ptest->y);
}
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,zona,first);
}
bool verif_update(punct *sursa,punct *&dest,double &unghi1,double unghi2, int zona,bool &first)
{
if ( first || ( zona == 1 && (unghi1 < unghi2)) || ( zona == 2 && (unghi1 > unghi2) ) || ( zona == 3 && (unghi1 < unghi2) ) || ( 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(nume_fisier,"w");
if ( f == 0 )
return;
fprintf(f,"%d\n",maxInf);
for(int i=(maxInf-1);i>=0;i--)
fprintf(f,"%f %f\n",INF[i].x,INF[i].y);
fclose(f);
}
bool citeste_fisier(char *nume_fisier)
{
FILE *f = fopen(nume_fisier,"r");
if ( f == 0 )
return 0;
double 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,"%lf %lf",&x,&y);
adauga_punct(V,maxPuncte,x,y);
}
fclose(f);
return 1;
}
void adauga_punct(punct *vector, int &maxElem,double x,double y)
{
vector[maxElem].x = x;
vector[maxElem].y = y;
vector[maxElem].verificat = false;
maxElem++;
}