Pagini recente » Cod sursa (job #764484) | Cod sursa (job #2856463) | Cod sursa (job #2980418) | Cod sursa (job #3182271) | Cod sursa (job #1334842)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int i,n,viz[100001],stiva[100001],x,k;
struct infas
{
double x,y;
}v[120001];
int cmp(infas A,infas B)
{
if(A.x==B.x)
return A.y<B.y;
else
return A.x<B.x;
}
double determinant(int A,int B,int C)
{
return (v[B].x-v[A].x)*(v[C].y-v[A].y)-(v[C].x-v[A].x)*(v[B].y-v[A].y);
}
void parcurgere(int x)
{
for(int i=1;i<=n;i++)
{
if(!viz[i])
{
viz[i]=1;
double z=determinant(stiva[x-1],stiva[x],i);
if(z < 0)
{
x++;k=x;
stiva[x]=i;
//parcurgere(x);
}
else
{
while(determinant(stiva[x-1],stiva[x],i)>0 && x>=1)
{
viz[stiva[x]]=0;
x--;
}viz[i]=1;stiva[++x]=i;
}
//parcurgere(x);
}
}
}
void parcurgere2()
{
for(int i=n;i>0;i--)
{
if(!viz[i])
{
viz[i]=1;
double z=determinant(stiva[x-1],stiva[x],i);
if(z < 0)
{
x++;k=x;
stiva[x]=i;
//parcurgere(x);
}
else
{
while(determinant(stiva[x-1],stiva[x],i)>0 && x>=1)
{
viz[stiva[x]]=0;
x--;
}viz[i]=1;stiva[++x]=i;
}
//parcurgere(x);
}
}
}
int main()
{
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
stiva[1]=1;stiva[2]=2;viz[2]=1;
parcurgere(2);
parcurgere2();
for(i=x-1;i>0;i--)
fout<<v[stiva[i]].x<<" "<<v[stiva[i]].y<<"\n";
return 0;
}