Pagini recente » Cod sursa (job #2308901) | Cod sursa (job #2520105) | Cod sursa (job #2205190) | Cod sursa (job #674855) | Cod sursa (job #363672)
Cod sursa(job #363672)
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int MAXN = 120000;
const int INF = 1000000000;
bool comp(int i, int j);
long double semn(int i1, int i2, int i3);
double x[MAXN], y[MAXN];
int pi, i, ind[MAXN], n, stiva[MAXN];
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&n);
x[0]=INF;
y[0]=INF;
int pctInit = 0;
for(i=1; i<=n; i++)
{
scanf("%lf %lf",&x[i],&y[i]);
if (x[i] < x[pctInit] || (x[i] == x[pctInit] && y[i] < y[pctInit]))
pctInit = i;
}
pi=pctInit;
for(i = 1;i <= n; ++i)
{
if (i != pctInit)
ind[++ind[0]] = i;
}
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(stiva[0]>=2 && semn(stiva[stiva[0]-1],stiva[stiva[0]],ind[i])>0)
stiva[0]--;
stiva[++stiva[0]] = ind[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;
}
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]);
}
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];
}