Cod sursa(job #607625)

Utilizator nashnash mit nash Data 12 august 2011 20:59:28
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 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 120005
vect vects[NMAX] , st[NMAX];
int n,k,p = 1;

int cmp(const vect& p1, const vect& p2) {
    vect p11 = p1 - vects[0];
    vect p22 = p2 - vects[0];
    if(p11.x * p22.y - p11.y * p22.x >=0.0f) return 1;
    if(p11.x * p22.y - p11.y * p22.x < 0.0f) return 0;
}

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 );
    
    int ind = 0;
    for(int i = 1 ; i < n ; i++) {
        if(vects[i].y < vects[ind].y) ind = i;
        if(vects[i].y == vects[ind].y && vects[i].x < vects[ind].x) ind = i ;
    }
    swap(vects[ind], vects[0]);
    
    sort(vects +1 , vects + n,cmp);
    k = 0; st[k] = vects[0]; 
    k = 1; st[k] = vects[1];
    
    for(int i = 1 ; i < n ; i++ ) {
        while( ( k > 0 ) && !( (st[k] - st[k-1]) < (vects[i] - st[k]) ) ) k--;
        st[++k] = vects[i];
    }
    
    printf("%d\n",k+1);
    for(int i =0  ; i <= k ; i++ )
        printf("%f %f\n", st[i].x , st[i].y );
    
    return 0;
}