Pagini recente » Cod sursa (job #1189117) | Cod sursa (job #1575397) | Cod sursa (job #1644857) | Cod sursa (job #2044974) | Cod sursa (job #263205)
Cod sursa(job #263205)
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
double x[120001],y[120001];
int puncte[120001],pfin[120001],i,n,ini,j;
bool pv( int i,int j)
{
return (double) ( x[i] - x[ini])*( y[j]-y[ini])< (double) (x[j]-x[ini]) * (y[i]-y[ini]);
}
long double ascutit ( int p1,int p2,int p3)
{
return (long double) ( x[p1]*y[p2]-x[p1]*y[p3]+x[p2]*y[p3]-x[p2]*y[p1]+x[p3]*y[p1]-x[p3]*y[p2]);
}
int main()
{
freopen( "infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&n);
for (i=1;i<=n;++i)
{
scanf("%lf %lf",&x[i],&y[i]);
if ( x[i]<x[ini] || x[i]==x[ini] && y[i]<y[ini] ) ini=i;
}
for (i=1;i<=n;++i)
{
if (i==ini) continue;
puncte[++puncte[0]]=i;
}
sort(puncte+1,puncte+puncte[0]+1,pv);
pfin[pfin[0]=1]=ini;
for (i=1;i<=puncte[0];++i)
{
if (puncte[i]==ini) continue;
while (pfin[0]>=2 && ascutit(pfin[pfin[0]-1],pfin[pfin[0]],puncte[i])>0) --pfin[0];
pfin[++pfin[0]]=puncte[i];
}
pfin[++pfin[0]]=ini;
printf("%d\n",pfin[0]-1);
reverse(pfin+1,pfin+pfin[0]+1);
for (i=1;i<pfin[0];++i)
{
printf("%lf %lf\n",x[pfin[i]],y[pfin[i]]);
}
return(0);
}