Pagini recente » Cod sursa (job #1552415) | Cod sursa (job #1539551) | Cod sursa (job #1723965) | Cod sursa (job #1491736) | Cod sursa (job #256738)
Cod sursa(job #256738)
#include <stdio.h>
#define MAX 120000
#define INF 1000000000
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");
double X[MAX],Y[MAX];
long double V[MAX];
int IND[MAX],ST[MAX];
int PI,N;
long double semn(int,int,int);
void quick(long,long);
long poz(long,long);
int main()
{
int i;
fscanf(fin,"%d\n",&N);
X[0]=INF;
Y[0]=INF;
int punct_initial=0;
for(i=1;i<=N;++i)
{
fscanf(fin,"%lf %lf",&X[i],&Y[i]);
if(X[i]<X[punct_initial] || (X[i]==X[punct_initial] && Y[i]<Y[punct_initial]))
punct_initial=i;
}
fclose(fin);
PI=punct_initial;
for(i=1;i<=N;++i)
{
if(i==punct_initial)
continue;
IND[++IND[0]]=i;
}
quick(1,IND[0]);
ST[ST[0]=1]=punct_initial;
for(i=1;i<=IND[0];++i)
{
if(IND[i]==punct_initial)
continue;
while(ST[0]>=2 && semn(ST[ST[0]-1],ST[ST[0]],IND[i]) > 0)
--ST[0];
ST[++ST[0]]=IND[i];
}
ST[++ST[0]]=punct_initial;
fprintf(fout,"%d\n",ST[0]-1);
for(i=ST[0]-1;i>0;i--)
fprintf(fout,"%lf %lf\n",X[ST[i]],Y[ST[i]]);
fclose(fout);
return 0;
}
long double semn(int i,int j,int k)
{
return (long double) (X[i]*Y[j]+X[j]*Y[k]+X[k]*Y[i])-(Y[i]*X[j]+Y[j]*X[k]+Y[k]*X[i]);
}
void quick(long st,long dr)
{
if(st<dr)
{
long k=poz(st,dr);
quick(st,k-1);
quick(k+1,dr);
}
}
long poz(long st,long dr)
{
long i=st;
long j=dr;
long ii=0;
long jj=-1;
long aux;
while(i<j)
{
if((X[IND[i]]-X[PI])*(Y[IND[j]]-Y[PI])>(X[IND[j]]-X[PI])*(Y[IND[i]]-Y[PI]))
{
aux=IND[i];
IND[i]=IND[j];
IND[j]=aux;
aux=ii;
ii=-jj;
jj=-aux;
}
i=i+ii;
j=j+jj;
}
return i;
}