Pagini recente » Cod sursa (job #1021828) | Cod sursa (job #2682769) | Cod sursa (job #829079) | Cod sursa (job #1801768) | Cod sursa (job #1829714)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1.e-12;
struct Point
{
double x,y;
} v[120005];
Point LL;
int h[120005];
double cross_product(Point P1, Point P2, Point P3)
{
return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
}
int ccw(Point P1, Point P2, Point P3)
{
double cp;
cp=cross_product(P1, P2, P3);
if(fabs(cp)<eps)
return 0;
else{
if(cp>=eps)
return 1;
else
return -1;
}
}
bool cmp(Point A, Point B)
{
int c=ccw(LL, A, B);
if(c==1)
return 1;
if(c==-1)
return 0;
}
int main()
{ freopen("infasuratoare.in", "r",stdin);
freopen("infasuratoare.out", "w",stdout);
int n,i,top;
scanf("%d",&n);
LL.x=LL.y=1000000005;
for(i=0; i<n; i++){
scanf("%lf%lf", &v[i].x, &v[i].y);
if(LL.y-v[i].y>=eps)
swap(LL,v[i]);
else{
if( fabs(LL.y-v[i].y)<eps)
if(LL.x-v[i].x>=eps)
swap(LL,v[i]);
}
}
v[0]=LL;
sort(v+1, v+n,cmp);
v[n]=LL;
h[0]=0;
h[1]=1;
top=1;
i=2;
while(i<=n){
if(ccw(v[h[top-1]], v[h[top]], v[i])>0){
h[++top]=i;
i++;
}
else
top--;
}
printf("%d\n", top);
for(i=0; i<top; i++)
printf("%lf %lf\n", v[h[i]].x, v[h[i]].y);
return 0;
}