Pagini recente » Cod sursa (job #149173) | Cod sursa (job #2397222) | Cod sursa (job #2301787) | Cod sursa (job #2724505) | Cod sursa (job #617590)
Cod sursa(job #617590)
#include<stdio.h>
#include<cmath>
#define PI 3.14159265
using namespace std;
struct punct
{
double x,y;
punct *leg;
};
int N;
punct *puncte, *P, *sol;
void Citire()
{
freopen ("infasuratoare.in","r",stdin);
scanf("%d",&N);
puncte = new punct;
scanf("%lf %lf",&puncte->x,&puncte->y);
puncte->leg=NULL;
for (int i=1;i<N;i++)
{
punct *p = new punct;
scanf("%lf %lf",&p->x,&p->y);
p->leg = puncte;
puncte = p;
}
fclose(stdin);
}
double Unghi(punct *C, punct *N)
{
double PC, CN, NP, unghiC;
PC = sqrt((C->x-P->x)*(C->x-P->x) + (C->y-P->y)*(C->y-P->y));
NP = sqrt((N->x-P->x)*(N->x-P->x) + (N->y-P->y)*(N->y-P->y));
CN = sqrt((C->x-N->x)*(C->x-N->x) + (C->y-N->y)*(C->y-N->y));
double cosx = (PC*PC + CN*CN - NP*NP)/(2*PC*CN);
unghiC = acos(cosx) * 180.0 / PI;
return unghiC;
}
punct *PunctUrmator(punct *C)
{
punct *punctMax, *p, *r, *prec;
double unghiTemp, unghiMax = -1;
for (p = puncte->leg, r = puncte; p != NULL ; p = p->leg, r=r->leg)
{
if (sol->leg == NULL) P = r;
else {P->x = sol->leg->x;P->y = sol->leg->y;}
unghiTemp = Unghi(C,p);
if (unghiTemp > unghiMax)
{
unghiMax = unghiTemp;
punctMax = p;
prec = r;
}
}
p=puncte;
unghiTemp = Unghi(C,p);
if (unghiTemp > unghiMax)
{
unghiMax = unghiTemp;
punctMax = p;
puncte = puncte->leg;
return punctMax;
}
P = C;
prec -> leg = punctMax->leg;
return punctMax;
}
punct *PunctInitial()
{
punct *punctStart = puncte, *p = puncte;
while (p!=NULL)
{
if (p->x > punctStart->x)
punctStart = p;
if (p->x == punctStart->x && p->y < punctStart->y)
punctStart = p;
p=p->leg;
}
return punctStart;
}
int main()
{
Citire();
int nrSol = 0;
punct *punctInitial = new punct,*p;
p = PunctInitial();
punctInitial->x=p->x;
punctInitial->y=p->y;
P = punctInitial;
sol = new punct;
sol->x = punctInitial->x;
sol->y = punctInitial->y;
sol->leg = NULL;
P->y ++;
punct *punctMobil = PunctUrmator(p);
punctMobil ->leg = sol;
sol = punctMobil;
nrSol = 2;
P = punctInitial;
do
{
punctMobil = PunctUrmator(punctMobil);
punctMobil ->leg = sol;
sol = punctMobil;
nrSol++;
}
while (punctMobil->x != punctInitial->x || punctMobil->y != punctInitial->y);
freopen("infasuratoare.out", "w", stdout);
printf ("%d\n",nrSol - 1);
p = sol;
punct *q = p->leg, *r = p->leg->leg;
p->leg = NULL;
while (r!=NULL)
{
q->leg = p;
p = q;
q = r;
r = r->leg;
}
q->leg = p;
while(q->leg != NULL)
{
printf("%.6lf %.6lf\n",q->x,q->y);
q = q->leg;
}
fclose(stdout);
return 0;
}