Pagini recente » Cod sursa (job #472647) | Cod sursa (job #1328591) | Cod sursa (job #1259759) | Cod sursa (job #1758106) | Cod sursa (job #617587)
Cod sursa(job #617587)
#include<stdio.h>
#include<cmath>
#define PI 3.14159265
using namespace std;
struct punct
{
double x,y;
bool vizitat;
};
int N;
punct puncte[120001], P, sol[120000];
void Citire()
{
freopen ("infasuratoare.in","r",stdin);
scanf("%d",&N);
int i;
for (i=0;i<N;i++)
{
scanf("%lf %lf",&puncte[i].x,&puncte[i].y);
puncte[i].vizitat = false;
}
fclose(stdin);
}
double Unghi(const punct &C,const 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);
return unghiC;
}
punct PunctUrmator(const punct &C)
{
int i, iTemp = 120001;
punct punctMax;
double unghiTemp, unghiMax = -1;
for (i=0;i<N;i++)
if (!puncte[i].vizitat)
{
unghiTemp = Unghi(C,puncte[i]);
if (unghiTemp > unghiMax)
{
unghiMax = unghiTemp;
punctMax = puncte[i];
iTemp = i;
}
}
P = C;
puncte[iTemp].vizitat = true;
return punctMax;
}
punct PunctInitial()
{
int i;
punct punctStart = puncte[0];
for (i=1;i<N;i++)
{
if (puncte[i].x > punctStart.x)
punctStart = puncte[i];
if (puncte[i].x == punctStart.x && puncte[i].y < punctStart.y)
punctStart = puncte[i];
}
return punctStart;
}
int main()
{
Citire();
int nrSol = 0;
punct punctInitial = PunctInitial();
P = punctInitial;
P.y ++;
sol[nrSol++] = punctInitial;
punct punctMobil = PunctUrmator(punctInitial);
sol[nrSol++] = punctMobil;
P = punctInitial;
do
{
punctMobil = PunctUrmator(punctMobil);
sol[nrSol++] = punctMobil;
}
while (punctMobil.x != punctInitial.x || punctMobil.y != punctInitial.y);
nrSol--;
freopen("infasuratoare.out", "w", stdout);
printf ("%d\n",nrSol);
for (int i=nrSol-1;i>=0;i--)
printf("%.6lf %.6lf\n",sol[i].x,sol[i].y);
fclose(stdout);
return 0;
}