Pagini recente » Cod sursa (job #2771125) | Cod sursa (job #3267111) | Cod sursa (job #2922988) | Cod sursa (job #473902) | Cod sursa (job #607523)
Cod sursa(job #607523)
#include <cstdio>
#include <algorithm>
using namespace std;
class vect {
public:
float x,y;
vect() {
x = y = 0.0f;
}
vect(int X,int Y):x(X),y(Y) {}
const int operator<(const vect& aux) const{
return x * aux.x - y * aux.x <= 0.0f;
}
vect operator-(const vect& aux) const {
return vect( x - aux.x , y - aux.y );
}
};
vect vects[120005] , st[120005];
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" , &vects[i].x , &vects[i].y );
sort(vects, vects + n);
k = 0; st[k] = vect();
k = 1; st[k] = vects[k];
for(int i = 2 ; i < n ; i++ ) {
while( ( k > 0 ) && ( vects[i] - st[k] < st[k] - st[k-1] ) )
k--;
st[++k] = vects[i];
}
int p = 1 ; while( st[p+1] - st[p] < st[p] - st[k] ) p++;
printf("%d\n",k-p+1);
for(int i = p ; i <= k ; i++ )
printf("%f %f\n", vects[i].x , vects[i].y );
return 0;
}