Pagini recente » Cod sursa (job #316677) | Cod sursa (job #762759) | Cod sursa (job #2847900) | Cod sursa (job #2478950) | Cod sursa (job #1014770)
#include <cstdio>
using namespace std;
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;
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;
else if(a[r[0]][0]==a[i][0]&&a[r[0]][1]>a[i][1]) r[0]=i;
}
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;
for(i=1;i<n;++i)
{
a[i][2]=(a[i][1]-a[0][1])/(a[i][0]-a[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[r[k]][1]-a[r[k-2]][1];
y=a[r[k-2]][0]-a[r[k]][0];
z=-a[r[k-2]][0]*x-a[r[k-2]][1]*y;
while(k>2&&((x*a[0][0]+y*a[0][1]+z)*(x*a[r[k-1]][0]+y*a[r[k-1]][1]+z)>=0))
{
r[k-1]=r[k];
--k;
x=a[r[k]][1]-a[r[k-2]][1];
y=a[r[k-2]][0]-a[r[k]][0];
z=-a[r[k-2]][0]*x-a[r[k-2]][1]*y;
}
++k;
}
printf("%d\n",k);
printf("%lf %lf\n",a[1][0],a[1][1]);
for(i=2;i<k;++i)
{
printf("%lf %lf\n",a[r[i]][0],a[r[i]][1]);
}
printf("%lf %lf\n",a[0][0],a[0][1]);
return 0;
}