Pagini recente » Cod sursa (job #2888967) | Cod sursa (job #709170)
Cod sursa(job #709170)
/*********************************
*Potrivirea lui Jarvis - O( N*H )*
*********************************/
#include <stdio.h>
#include <string.h>
#define maxN 120001
struct punct
{
double x,y;
}P[maxN],pi,H[maxN];
int use[maxN];
inline int unghi(punct a,punct b,punct c)
{
return (b.x-a.x)*(c.y-a.y)<(c.x-a.x)*(b.y-a.y);
}
int main()
{
int N;
freopen("infasuratoare.in","r",stdin);
scanf("%d",&N);
for(int i=1;i<=N;++i) scanf("%lf%lf",&P[i].x,&P[i].y);
pi=P[1];
int pos=1;
for(int i=2;i<=N;++i)
if(P[i].x<pi.x)
{
pi=P[i];
pos=i;
}
else
if(P[i].x==pi.x&&P[i].y<pi.y)
{
pi=P[i];
pos=i;
}
memset(use,0,sizeof(use));
use[pos]=1;
int aux=pos;
int cnt=0;
H[++cnt]=pi;
while(1)
{
int to=0;
for(int i=1;i<=N;++i)
if(!use[i])
{
if(to==0) to=i;
else
if(unghi(P[pos],P[to],P[i])) to=i;
}
if(unghi(P[pos],P[to],P[aux])) to=aux;
if(to==aux) break;
pos=to;
use[pos]=1;
H[++cnt]=P[pos];
}
freopen("infasuratoare.out","w",stdout);
printf("%d\n",cnt);
for(int i=1;i<=cnt;++i)
printf("%.7lf %.7lf\n",H[i].x,H[i].y);
return 0;
}