Pagini recente » Cod sursa (job #3179993) | Cod sursa (job #2680748) | Cod sursa (job #2127936) | Cod sursa (job #2680873) | Cod sursa (job #714348)
Cod sursa(job #714348)
#include <fstream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=120005;
struct punct{double x,y;} v[N],a[N],b[N];
int A,B,n;
ifstream in("infasuratoare.in");
inline bool cmp(const punct &a,const punct &b)
{
return a.x<b.x || a.x==b.x && a.y<b.y;
}
inline bool panta(punct a,punct b,punct c)
{
return (b.y-a.y)*(c.x-a.x)<(b.x-a.x)*(c.y-a.y);
}
int main()
{
freopen("infasuratoare.out","w",stdout);
int i;
in>>n;
for (i=1;i<=n;i++)
in>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
a[++A]=v[1];
for (i=2;i<=n;i++)
{
while (A>1 && panta(a[A-1],a[A],v[i]))
A--;
a[++A]=v[i];
}
A--;
b[++B]=v[n];
for (i=n-1;i;i--)
{
while (B>1 && panta(b[B-1],b[B],v[i]))
B--;
b[++B]=v[i];
}
B--;
printf("%d\n",A+B);
for (i=B;i;i--)
printf("%.6lf %.6lf\n",b[i].x,b[i].y);
for (i=A;i;i--)
printf("%.6lf %.6lf\n",a[i].x,a[i].y);
return 0;
}