Pagini recente » Cod sursa (job #2055939) | Cod sursa (job #1082879) | Cod sursa (job #2887263) | Cod sursa (job #965585) | Cod sursa (job #1411331)
#include <cstdio>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
typedef pair<double, double> pct;
pct p[120005],S[120005];
int n,i,minx,miny,k,poz=1;
int D(pct x,pct y,pct z)
{
double X=0;
X=(y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);
return X;
}
bool cmp(pct A,pct B)
{
return D(p[1],A,B)<0;
}
int main()
{
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%lf %lf\n",&p[i].x,&p[i].y);
for(i=2;i<=n;i++)
if(p[i]<p[poz])
poz=i;
swap(p[1],p[poz]);
sort(p+2,p+n+1,cmp);
S[1]=p[1];
S[2]=p[2];
k=2;
for(i=3;i<=n;i++)
{
while(k>=2 and D(S[k-1],S[k],p[i])>0)
k--;
S[++k]=p[i];
}
fprintf(g,"%d\n",k);
for(i=k;i>=1;i--)
fprintf(g,"%0.6f %0.6f\n",S[i].x,S[i].y);
return 0;
}