Pagini recente » Cod sursa (job #2791296) | Cod sursa (job #1645362) | Cod sursa (job #1701958) | Cod sursa (job #867265) | Cod sursa (job #628255)
Cod sursa(job #628255)
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax = 120005;
const int inf = (2e9);
int n,pi,punct_init,i,st[nmax],ind[nmax];
double x[nmax],y[nmax];
bool cmp(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];
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
x[0]=y[0]=inf;
punct_init=0;
for (i=1; i<=n; ++i)
{
f>>x[i]>>y[i];
if (x[i]<x[punct_init] || (x[i]==x[punct_init] && y[i]<y[punct_init]))
punct_init=i;
}
pi=punct_init;
for (i=1; i<=n; ++i)
if (i!=punct_init)
ind[++ind[0]] = i;
sort(ind+1, ind+ind[0]+1, cmp);
st[++st[0]] = punct_init;
for (i=1; i<=ind[0]; ++i)
{
if (ind[i]!=punct_init)
while (st[0]>=2 && semn(st[st[0]-1],st[st[0]],ind[i]) > 0)
--st[0];
st[++st[0]] = ind[i];
}
g<<st[0]<<'\n';
for (i=st[0]; i>=1; --i)
g<<x[st[i]]<<' '<<y[st[i]]<<'\n';
return 0;
}