Cod sursa(job #403692)
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stdlib.h>
using namespace std;
const int NMAX=120002;
const double oo=1000000001;
double X[NMAX],Y[NMAX];
int n,ind[NMAX],psj,S[NMAX];
void citire()
{ FILE *fin=fopen("infasuratoare.in","r");
fscanf(fin,"%d",&n);
int i;
psj=0; X[0]=oo; Y[0]=oo;
for (i=1;i<=n;i++)
{
fscanf(fin,"%lf%lf",&X[i],&Y[i]);
if (X[i]<X[psj] || (X[i]==X[psj] && Y[i]<Y[psj])) psj=i;
}
fclose(fin);
}
bool upolar(int i,int j)
{
return (double)(X[i] - X[psj]) * (Y[j] - Y[psj]) > (double)(X[j] - X[psj]) * (Y[i] - Y[psj]);
}
double sens(int p1, int p2, int p3)
{
return ((X[p2]-X[p1])*(Y[p3]-Y[p1])-(X[p3]-X[p1])*(Y[p2]-Y[p1]));
}
int main()
{
citire();
ind[0]=0;
int i;
for (i=1;i<=n;++i)
if (i!=psj) ind[++ind[0]]=i;
sort(ind+1,ind+1+ind[0],upolar);
int ns=1;
S[1]=psj;
for (i=1;i<=ind[0];++i)
{
while (ns>1 && sens(S[ns-1],S[ns],ind[i])<=0) --ns;
S[++ns]=ind[i];
}
FILE *fout=fopen("infasuratoare.out","w");
fprintf(fout,"%d\n",ns);
for (i=1;i<=ns;++i)
fprintf(fout,"%lf %lf\n",X[S[i]],Y[S[i]]);
fclose(fout);
return 0;
}