Pagini recente » Cod sursa (job #3134474) | Cod sursa (job #2316912) | Cod sursa (job #1664332) | Cod sursa (job #1944807) | Cod sursa (job #2280024)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct
{
double x,y,r,t,xprev,yprev;
};
Punct A1,B1,P1;
int pozpunctdreapta(Punct A,Punct B,Punct P);
double crossproduct(Punct A,Punct B,Punct P);
int n,i,dx,dy;
Punct stiva[120005];
int capstiva;
Punct Pmarg,X;
Punct Mem[120005];
bool ok;
int main()
{
fin>>n;
Pmarg.x=999999;
Pmarg.y=999999;
for (i=1;i<=n;i++)
{
fin>>X.x>>X.y;
X.xprev=X.x;
X.yprev=X.y;
Mem[i]=X;
if (X.x<Pmarg.x)
Pmarg=X;
else if (X.x==Pmarg.x&&X.y<Pmarg.y)
Pmarg=X;
}
for (i=1;i<=n;i++)
{
dx=Mem[i].x-Pmarg.x;
dy=Mem[i].y-Pmarg.y;
Mem[i].r=dx*dx+dy*dy;
if (dx!=0)
Mem[i].t=dy/dx;
else
Mem[i].t=99999999;
Mem[i].x=dx;
Mem[i].y=dy;
}
ok=1;
while (ok==1)
{
ok=0;
for (i=1;i<n;i++)
{
if (Mem[i].t>Mem[i+1].t)
{
ok=1;
swap(Mem[i],Mem[i+1]);
}
else if ((Mem[i].t==Mem[i+1].t)&&(Mem[i].r>Mem[i+1].r))
{
ok=1;
swap(Mem[i],Mem[i+1]);
}
}
}
capstiva=2;
stiva[1]=Mem[1];
stiva[2]=Mem[2];
for (i=3;i<=n;i++)
{
while (crossproduct(stiva[capstiva-1],stiva[capstiva],Mem[i])<=0&&capstiva>=3)
capstiva--;
capstiva++;
stiva[capstiva]=Mem[i];
}
fout<<capstiva<<"\n";
for (i=1;i<=capstiva;i++)
fout<<fixed<<setprecision(6)<<stiva[i].xprev<<" "<<stiva[i].yprev<<"\n";
return 0;
}
int pozpunctdreapta(Punct A,Punct B,Punct P)
{
if (A.x==B.x)
return P.x-A.x;
else if (A.y==B.y)
return P.x-A.y;
else
return (P.x-A.x)*(B.y-A.y)-(P.y-A.y)*(B.x-A.x);
} // Nota x,yA sunt x,y minime iar x,y B sunt x,y maxime.
double crossproduct(Punct A,Punct B,Punct P)
{
return (A.x-P.x)*(B.y-P.y)-(B.x-P.x)*(A.y-P.y);
}