Pagini recente » Cod sursa (job #315076) | Borderou de evaluare (job #2985483) | Borderou de evaluare (job #2986764) | Cod sursa (job #607444)
Cod sursa(job #607444)
#include <cstdio>
#include <algorithm>
using namespace std;
class point {
public:
float x,y;
point() {
x = y = 0.0f;
}
//const int operator<=(const point& aux) const{
// return x * aux.x - y * aux.x >= 0.0f;
//}
};
int cross(const point& p1 ,const point& p2) {
return p1.x * p2.y - p1.y * p2.x >= 0.0f ;
}
point points[120005] ;
point st[12005];
int n,k;
int main() {
freopen("infasuratoare.in" , "r" , stdin );
freopen("infasuratoare.out", "w" , stdout);
scanf("%d",&n);
for( int i = 0 ; i < n ; i++ )
scanf("%f %f" , &points[i].x , &points[i].y );
sort(points, points + n , cross );
k = 0 ; st[k] = points[0]; k = 1;
for( int i = 1 ; i < n ; i++ ) {
while( ( k >= 0 ) && ( cross( st[k] , points[i] ) < 0.0f ) )
k--;
st[k] = points[i];
}
printf("%d\n",k);
for(int i = 1 ; i <= k ; i++ )
printf("%f %f\n", points[i].x , points[i].y );
return 0;
}