Cod sursa(job #607611)

Utilizator nashnash mit nash Data 12 august 2011 19:53:59
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <algorithm>

using namespace std;

class vect {
public:
    float x,y;
    
    vect():x(0.0f),y(0.0f) {}
    
    vect(int X,int Y):x(X),y(Y) {}
    
    const int operator<(const vect& aux)  const{
        if(x * aux.y - y * aux.x >=0.0f) return 1;
        if(x * aux.y - y * aux.x < 0.0f) return 0;
    }
    
    vect operator-(const vect& aux) const {
        return vect( x - aux.x , y - aux.y );
    }
};

#define NMAX 10
vect vects[NMAX] , st[NMAX];
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[0];
    
    for(int i = 1 ; i < n ; i++ ) {
        while( ( k > 0 ) &&  
               !( (st[k] - st[k-1]) < (vects[i] - st[k]) ) ) 
            k--;
        st[++k] = vects[i];
    }
    
    int p = 1 ; 
    while( !(st[p] - st[k] < st[p+1] - st[p]) ) 
        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;
}