Pagini recente » Cod sursa (job #1119612) | Cod sursa (job #2740340) | Cod sursa (job #1281882) | Cod sursa (job #1635455) | Cod sursa (job #1887757)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct punct
{
double x,y;
} vPuncte[120005],stiva[120005];
int n;
void citire()
{
double st=0x3f3f3f;
int indice;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%lf%lf",&vPuncte[i].x,&vPuncte[i].y);
if(st>=vPuncte[i].x)
{
if(st==vPuncte[i].x)
{
if(vPuncte[indice].y>vPuncte[i].y)
{
st=vPuncte[i].x;
indice=i;
}
}
else
{
st=vPuncte[i].x;
indice=i;
}
}
}
swap(vPuncte[indice],vPuncte[1]);
}
double calculDet(punct p1,punct p2,punct p3)
{
return(p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p2.y*p3.x-p3.y*p1.x-p1.y*p2.x);
}
bool cmp(punct p1,punct p2)
{
if(calculDet(vPuncte[1],p1,p2)<0)
return false;
return true;
}
void solve()
{
sort(vPuncte+2,vPuncte+n+1,cmp);
/*for(int i=1;i<=n;i++)
{
printf("%lf %lf\n",vPuncte[i].x,vPuncte[i].y);
}
*/
int indice_stiva=2;
stiva[1]=vPuncte[1];
stiva[2]=vPuncte[2];
for(int i=3; i<=n; i++)
{
if(indice_stiva>=2)
{
if(calculDet(stiva[indice_stiva-1],stiva[indice_stiva],vPuncte[i])>0)
{
stiva[++indice_stiva]=vPuncte[i];
i++;
}
else indice_stiva--;
i--;
}
else
stiva[++indice_stiva]=vPuncte[i];
}
printf("%d\n",indice_stiva);
for(int i=1; i<=indice_stiva; i++)
printf("%.6lf %.6lf\n",stiva[i].x,stiva[i].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
solve();
return 0;
}