Pagini recente » Cod sursa (job #2699286) | Cod sursa (job #1411353)
#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(const pct& x,const pct& y,const pct& z)
{
return (y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);
}
bool cmp(const pct& A,const 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.9f %0.9f\n",S[i].x,S[i].y);
return 0;
}