Pagini recente » Cod sursa (job #3258986) | Cod sursa (job #578158) | Cod sursa (job #2234199) | Cod sursa (job #491763) | Cod sursa (job #1014668)
#include <cstdio>
using namespace std;
long double a[120000][3];
int r[120000];
void qs(int stanga, int dreapta)
{
int i, j;
long double mijloc, aux; // variabilele
i=stanga; // initializarea
j=dreapta; // indicilor
mijloc=a[(stanga+dreapta)/2][2]; // initializarea variabilei - pivot
while(i<=j)
{
while(a[i][2]<mijloc) // apropierea i-ului de mijloc
i++;
while(a[j][2]>mijloc) // apropierea j-ului de mijloc
j--;
if(i<=j) //conditia efectuarii operatiei de interschimbare
{
aux=a[i][2];
a[i][2]=a[j][2]; // operatia de interschimbare
a[j][2]=aux;
aux=a[i][1];
a[i][1]=a[j][1]; // operatia de interschimbare
a[j][1]=aux;
aux=a[i][0];
a[i][0]=a[j][0]; // operatia de interschimbare
a[j][0]=aux;
i++;
j--;
}
}
if(stanga<j) //recursivitatea
qs(stanga, j); // in partea stanga
if(i<dreapta)
qs(i, dreapta); // in partea dreapta
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int i,k,n;
long double x,y,z;
scanf("%d",&n);
scanf("%Lf%Lf",&a[0][0],&a[0][1]);
r[0]=0;
for(i=1;i<n;++i)
{
scanf("%Lf%Lf",&a[i][0],&a[i][1]);
if(a[r[0]][0]>a[i][0]) r[0]=i;
}
for(i=0;i<r[0];++i)
{
a[i][2]=(a[i][1]-a[r[0]][1])/(a[i][0]-a[r[0]][0]);
}
for(i=r[0]+1;i<n;++i)
{
a[i][2]=(a[i][1]-a[r[0]][1])/(a[i][0]-a[r[0]][0]);
}
x=a[r[0]][0];
a[r[0]][0]=a[0][0];
a[0][0]=x;
x=a[r[0]][1];
a[r[0]][1]=a[0][1];
a[0][1]=x;
r[0]=0;
qs(1,n-1);
r[1]=1;
y=a[1][2];
x=(a[1][0]-a[0][0])*(a[1][0]-a[0][0])+(a[1][1]-a[0][1])*(a[1][1]-a[0][1]);
i=2;
while(a[i][2]==y)
{
z=(a[i][0]-a[0][0])*(a[i][0]-a[0][0])+(a[i][1]-a[0][1])*(a[i][1]-a[0][1]);
if(z>x)
{
x=z;
r[1]=i;
}
++i;
}
x=a[r[1]][0];
a[r[1]][0]=a[1][0];
a[1][0]=x;
x=a[r[1]][1];
a[r[1]][1]=a[1][1];
a[1][1]=x;
k=2;
for(i=2;i<n;++i)
{
r[k]=i;
x=a[k][1]-a[k-2][1];
y=a[k-2][0]-a[k][0];
z=-a[k-2][0]*x-a[k-2][1]*y;
while(k>2&&((x*a[0][0]+y*a[0][1]+z)*(x*a[k-1][0]+y*a[k-1][1]+z)>=0))
{
r[k-1]=r[k];
--k;
x=a[k][1]-a[k-2][1];
y=a[k-2][0]-a[k][0];
z=-a[k-2][0]*x-a[k-2][1]*y;
}
++k;
}
printf("%d\n",k);
for(i=0;i<k;++i)
{
printf("%Lf %Lf\n",a[r[i]][0],a[r[i]][1]);
}
return 0;
}