Pagini recente » Cod sursa (job #648688) | Cod sursa (job #1074023) | Cod sursa (job #456459) | Cod sursa (job #2749594) | Cod sursa (job #1242239)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define PDD pair < double , double >
#define NMAX 120500
#define F first
#define S second
PDD P[NMAX];
int _i,i,N,f;
int Q[NMAX];
double w(PDD A,PDD B,PDD C)
{
return (A.F-C.F)*(B.S-C.S)-(B.F-C.F)*(A.S-C.S);
}
bool compare(PDD A,PDD B)
{
return (w(P[1],A,B)>0);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
for (i=_i=1,scanf("%d",&N);i<=N;++i)
{
scanf("%lf%lf",&P[i].F,&P[i].S);
if (P[i]<P[_i]) _i=i;
}
swap(P[1],P[_i]);
sort(P+2,P+N+1,compare);
Q[1]=1,Q[2]=f=2;
for (i=3;i<=N;++i)
{
while (f>=2 && w(P[Q[f]],P[Q[f-1]],P[i])>=0)
--f;
Q[++f]=i;
}
printf("%d\n",f);
for (i=1;i<=f;++i)
printf("%.7lf %.7lf\n",P[Q[i]].F,P[Q[i]].S);
return 0;
}