Pagini recente » Cod sursa (job #2341426) | Cod sursa (job #1308343) | Cod sursa (job #1886055) | Cod sursa (job #180217) | Cod sursa (job #363675)
Cod sursa(job #363675)
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
const int NMAX=120000; ///////////////////////////10010
const int INF=1000000000;
bool comp(int i, int j);
long double semn(int i1, int i2, int i3);
double x[NMAX], y[NMAX];
int pctInit=0, i, pi, n, ind[NMAX], stiva[NMAX];
int main()
{
freopen("infasuratoare.in", "r", stdin); ///////////////////
freopen("infasuratoare.out", "w", stdout); ////////////////////
scanf("%d", &n);
x[0]=INF;
y[0]=INF;
for (i=1; i<=n; i++)
{
scanf("%lf %lf", &x[i], &y[i]); //////////%ld
if ((x[pctInit]>x[i])||((x[pctInit]==x[i])&&(y[pctInit]>y[i])))
pctInit=i;
}//for i
for (i=1; i<=n; i++)
{
if (i!=pctInit)
ind[++ind[0]]=i;
}//for i
pi=pctInit;
sort(ind+1, ind+ind[0]+1, comp);
stiva[0]=1;
stiva[stiva[0]]=pctInit;
for (i=1; i<=ind[0]; i++)
{
if (ind[i]!=pctInit)
while ((semn(stiva[stiva[0]-1], stiva[stiva[0]], ind[i])>0)&&(stiva[0]>1))
stiva[0]--;
stiva[++stiva[0]]=ind[i];
}//for i
stiva[++stiva[0]]=pctInit;
printf("%d\n",stiva[0]-1);
reverse(stiva+1, stiva+stiva[0]+1);
for (i=1;i<stiva[0]; i++)
printf("%lf %lf\n",x[stiva[i]],y[stiva[i]]);
return 0;
}//main
bool comp(int i, int j)
{
return (double)(x[i]-x[pi])*(y[j]-y[pi]) < (double)(x[j]-x[pi])*(y[i]-y[pi]);
}//comp
long double semn(int i1, int i2, int i3)
{
return (long 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];
}//semn