Pagini recente » Cod sursa (job #1638408) | Cod sursa (job #85405) | Cod sursa (job #3140622) | Cod sursa (job #2278258) | Cod sursa (job #274398)
Cod sursa(job #274398)
#include <fstream.h>
#include <iomanip.h>
#include <values.h>
int n,minx=MAXINT,miny,k;
float x[120000],y[120000],xf[120000],yf[120000];
void cit()
{
int i;
ifstream fin("infasuratoare.in");
fin>>n;
for(i=1;i<=n;i++)
{
fin>>x[i]>>y[i];
if(x[i]<minx)
{
minx=x[i]; miny=y[i];
}
else
if(x[i]==minx && y[i]<miny)
miny=y[i];
}
fin.close();
}
void trans()
{
int i;
for(i=1;i<=n;i++)
{
x[i]-=minx;
y[i]-=miny;
}
}
void poz(int li,int ls)
{
int i,j,ii,jj,c;
float di,dj;
ii=0; jj=-1;
i=li; j=ls;
while(i<=j)
{
if(x[i]==0)
{
di=MAXINT;
if(x[j]==0)
dj=MAXINT;
else
dj=y[j]/x[j];
}
else
if(x[j]==0)
{
dj=MAXINT;
if(x[i]==0)
di=MAXINT;
else
di=y[i]/x[i];
}
else
{
di=y[i]/x[i];
dj=y[j]/x[j];
}
if(di>dj)
{
c=x[i]; x[i]=x[j]; x[j]=c;
c=y[i]; y[i]=y[j]; y[j]=c;
c=ii;
ii=-jj;
jj=-c;
}
else
if(di==dj)
{
di=x[i]*x[i]+y[i]*y[i];
dj=x[j]*x[j]+y[j]*y[j];
if(di>dj)
{
c=x[i]; x[i]=x[j]; x[j]=c;
c=y[i]; y[i]=y[j]; y[j]=c;
c=ii;
ii=-jj;
jj=-c;
}
}
i+=ii;
j+=jj;
}
k=i;
}
void quick(int li,int ls)
{
if(li<ls)
{
poz(li,ls);
quick(li,k-1);
quick(k+1,ls);
}
}
void afis()
{
int i;
ofstream fout("infasuratoare.out");
fout<<k+1<<'\n';
fout.precision(6);
for(i=1;i<=k+1;i++)
fout<<setiosflags(ios::showpoint)<<xf[i]+minx<<" "<<yf[i]+miny<<'\n';
fout.close();
}
int det(int i,int j,int k)
{
int d,x1,y1,x2,y2,x3,y3;
x1=xf[i]; y1=yf[i];
x2=xf[j]; y2=yf[j];
x3=x[k]; y3=y[k];
d=x1*y2+x2*y3+x3*y1-x3*y2-x2*y1-x1*y3;
return d;
}
void parc()
{
int i,d;
k=2;
xf[1]=x[1]; yf[1]=y[1];
xf[2]=x[2]; yf[2]=y[2];
for(i=3;i<=n;i++)
{
d=det(k-1,k,i);
while(d<0 && k>1)
{
k--;
d=det(k-1,k,i);
}
k++;
xf[k]=x[i]; yf[k]=y[i];
}
d=det(k-1,k,1);
while(d<0)
{
k--;
d=det(k-1,k,1);
}
}
int main()
{
cit();
trans();
quick(1,n);
parc();
afis();
return 0;
}