Pagini recente » Cod sursa (job #2463858) | Cod sursa (job #727290) | Cod sursa (job #1412713) | Cod sursa (job #2715361) | Cod sursa (job #729873)
Cod sursa(job #729873)
#include<cstdio>
#include<algorithm>
using namespace std;
#define NMAX 120005
#define INF 2000000000
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
long N, PCT[NMAX],S[NMAX],init,vf;
double X[NMAX],Y[NMAX],st=INF,jos=INF;
struct cmp {
bool operator() (long i,long j)
{ return ( X[i]-X[init]) * (Y[j]-Y[init]) < (X[j]-X[init]) *(Y[i]-Y[init]) ;}
};
double unghi_stanga( long i1, long i2,long i3)
{
return (double)X[i1] * Y[i2] + X[i2] * Y[i3] + X[i3] * Y[i1] - Y[i1] * X[i2] - Y[i2] * X[i3] - Y[i3] * X[i1];
}
int main()
{
fscanf(f,"%ld",&N);
for (long i=1;i<=N;i++)
{ fscanf(f,"%lf%lf", &X[i], &Y[i]);
if (X[i]<st || ( X[i]==st && Y[i] < jos ) )
{ init=i;
st=X[i]; jos=Y[i];
}
}
for (long i=1;i<=N;i++)
{ if (i==init) continue;
PCT[ ++PCT[0] ] = i;
}
sort ( PCT+1, PCT+PCT[0]+1 , cmp() );
vf=3;
S[1]=init;
S[2]= PCT[1];
S[3]= PCT[2];
for (long i=3;i<=PCT[0];i++)
{ long p = PCT[i];
while( vf>=2 && unghi_stanga ( S[vf],S[vf-1],p) <0 ) vf--;
S[++vf]=p;
}
fprintf(g,"%ld\n",vf);
for (long i=vf;i>=1;i--)
fprintf(g,"%lf %lf\n",X[S[i]],Y[S[i]]);
return 0;}