Pagini recente » Cod sursa (job #2912678) | Cod sursa (job #3281818) | Cod sursa (job #9008) | Cod sursa (job #924740) | Cod sursa (job #795846)
Cod sursa(job #795846)
#include <stdio.h>
#include <algorithm>
#define NMAX 120005
#define pdd pair <double,double>
#define x first
#define y second
using namespace std;
int n,r;
pdd A[NMAX],st[NMAX];
void read()
{
scanf("%d",&n);
int i;
for (i=1; i<=n; i++)
scanf("%lf%lf",&A[i].x,&A[i].y);
}
bool comp(pdd a,pdd b)
{
if (a.y<b.y)
return 1;
if (a.y>b.y)
return 0;
if (a.x<b.x)
return 1;
return 0;
}
inline int semn(pdd a,pdd b,pdd c)
{
double a1=a.y-b.y;
double b1=b.x-a.x;
double c1=a.x*b.y-b.x*a.y;
return (a1*c.x+b1*c.y+c1)<0;
}
void solve()
{
sort(A+1,A+n+1,comp);
st[++r]=A[1]; st[++r]=A[2];
int i;
for (i=3; i<=n; i++)
{
while (r>=2 && semn(st[r-1],st[r],A[i]))
r--;
st[++r]=A[i];
}
for (i=n-1; i>=1; i--)
{
while (r>=2 && semn(st[r-1],st[r],A[i]))
r--;
st[++r]=A[i];
}
r--;
printf("%d\n",r);
for (i=1; i<=r; i++)
printf("%lf %lf\n",st[i].x,st[i].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
sort(A+1,A+n+1);
solve();
return 0;
}