Pagini recente » Cod sursa (job #675094) | Cod sursa (job #1570069) | Cod sursa (job #2496223) | Cod sursa (job #981567) | Cod sursa (job #294941)
Cod sursa(job #294941)
#include <cstdio>
#include <algorithm>
#define dim 120100
using namespace std;
int n, s[dim], ind[dim], in;
double x[dim], y[dim];
long double semn(int n1, int n2, int n3)
{
return (long double)x[n1]*y[n2]+x[n2]*y[n3]+x[n3]*y[n1]-y[n1]*x[n2]-y[n2]*x[n3]-y[n3]*x[n1];
}
bool cmpf(int i, int j)
{
return (double)(x[i]-x[in])*(y[j]-y[in])<(double)(x[j]-x[in])*(y[i]-y[in]);
}
void graham()
{
int i;
s[1]=in;
s[0]=1;
for (i=1; i<=ind[0]; i++)
{
while (s[0]>=2 && semn(s[s[0]-1], s[s[0]], ind[i])>0)
--s[0];
s[++s[0]]=ind[i];
}
s[++s[0]]=in;
}
int main()
{
int i;
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d\n", &n);
x[0]=10e11;
y[0]=10e11;
in=0;
for (i=1; i<=n; i++)
{
scanf("%lf %lf\n", &x[i], &y[i]);
if (x[i]<x[in] || (x[i]==x[in] && y[i]<y[n])) in=i;
}
for (i=1; i<=n; i++)
{
if (i==in) continue;
ind[++ind[0]]=i;
}
sort(ind+1, ind+ind[0]+1, cmpf);
graham();
printf("%d\n", s[0]-1);
reverse(s+1, s+s[0]+1);
for (i=1; i<s[0]; i++) printf("%lf %lf\n", x[s[i]], y[s[i]]);
return 0;
}