Cod sursa(job #607523)

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