Pagini recente » Cod sursa (job #3219168) | Cod sursa (job #2672294) | Cod sursa (job #2447438) | Cod sursa (job #1215435) | Cod sursa (job #1098799)
#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int MAXN=120005;
typedef pair<double,double> point;
int n,head;
point p[MAXN],stack[MAXN];
inline void push(point a){stack[++head]=a;}
inline void pop(){--head;}
double cross_product(point O, point A, point B)
{
point OA,OB;
OA.x=A.x-O.x;
OA.y=A.y-O.y;
OB.x=B.x-O.x;
OB.y=B.y-O.y;
return OA.x*OB.y-OA.y*OB.x;
}
bool compare_vectors(point A, point B)
{
return cross_product(p[1],A,B)<0;
}
int main()
{
int i,pos=1;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=1; i<=n; ++i)
scanf("%lf%lf",&p[i].x,&p[i].y);
//sorteaza punctele dupa produsul vectorial OA, OB unde O=p[1]
for (i=1; i<=n; ++i)
{
if (p[pos]>p[i])
pos=i;
}
swap(p[1],p[pos]);
sort(p+2,p+n+1,compare_vectors);
//infasuratoarea convexa
push(p[1]);
push(p[2]);
for (i=3; i<=n; ++i)
{
while (head>=2 && cross_product(stack[head-1],stack[head],p[i])>0)
pop();
push(p[i]);
}
printf("%d\n",head);
for (i=head; i>0; --i)
printf("%.6lf %.6lf\n",stack[i].x,stack[i].y);
return 0;
}