Pagini recente » Cod sursa (job #485178) | Cod sursa (job #2187127) | Cod sursa (job #246796) | Cod sursa (job #1827695) | Cod sursa (job #250274)
Cod sursa(job #250274)
#include <stdio.h>
#include <algorithm>
#define absd(a) ((a)<0?-(a):(a))
#define eps 0.0000000001
using namespace std;
struct point{double x,y;};
int n,i,p,q,H[120005],minmax,maxmin;
point a[120005];
bool cmp (point P1, point P2){
if (absd(P1.x-P2.x)<eps)return (P1.y<P2.y);
else return (P1.x<P2.x);
}
inline double isLeft(point P1, point P2,point P){
return (P2.x-P1.x)*(P.y-P1.y)- (P.x-P1.x)*(P2.y-P1.y);
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%ld",&n);
for (i=1;i<=n;++i) scanf("%lf %lf\n",&a[i].x,&a[i].y);
sort (a+1,a+n+1,cmp);
/*for (i=1;i<=n;++i)
printf("%lf %lf\n",a[i].x,a[i].y);*/
//get the min,max and max,min points
for (i=1; i<=n && a[i].x==a[1].x ;++i);minmax=i-1;
for (i=n; i && a[i].x==a[n].x ;--i);maxmin=i+1;
//lower Hull
p=1; q=0; H[++q]=1;//min,min point...n is the max,max point
i=minmax;
while ( ++i <= maxmin ){
if ( isLeft( a[1] , a[maxmin] , a[i] ) >=0 && i < maxmin ) continue;
while (q>1){
if ( isLeft( a[ H[q-1] ], a[ H[q] ], a[i] ) > 0 ) break;
q--;
}
H[++q]=i;
}
//upper Hull
if ( maxmin != n ) H[++q] = n;
p = q;
i = maxmin;
while ( --i >= minmax ){
if ( isLeft( a[n], a[minmax], a[i] ) >= 0 && i > minmax )continue;
while (q > p){
if ( isLeft( a[ H[q-1] ], a[ H[q] ], a[i] ) > 0 )break;
q--;
}
H[++q]=i;
}
//if (minmax!=1) H[++q] = 1;
printf("%ld\n",q);
for (i=1;i<=q;++i)
printf("%lf %lf\n",a[H[i]].x , a[H[i]].y );
return 0;
}