Cod sursa(job #607444)

Utilizator nashnash mit nash Data 12 august 2011 01:45:40
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#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;
}