Cod sursa(job #653446)

Utilizator slycerdan dragomir slycer Data 28 decembrie 2011 01:21:39
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.04 kb
/* 
 * File:   Infasuratoareconvexa.cpp
 * Author: slycer
 *
 * Created on December 25, 2011, 7:49 PM
 */

#include <cstdlib>
#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

class Punct {
public:
    double x, y;

    Punct(double x, double y) {
        this->x = x;
        this->y = y;
    }
    
    void print(){
        cout << x << " " << y ;
    }
    
    
    double slope( Punct &punct ){
        if ( x - punct.x != 0 ){
                return ( y - punct.y)/( x - punct.x );
        } else {
            return abs( y - punct.y ); 
        }
    }
    
    
};

double angle( Punct base, Punct r ){
    double a = r.x - base.x; 
    double b = r.y - base.y; 
    if ( a == 0 ) {
        if ( b<0){
            return -1; 
        }  else {
            return 1; 
        }
    } 
    return b/a;//atan2(a,b);
}

double area( Punct a, Punct b, Punct c ){
    return ( a.x - c.x ) * ( b.y - a.y ) - ( a.x - b.x ) * ( c.y - a.y );
}

Punct minim(0,0); 
double distanta( Punct a, Punct b ){
    double unu = (a.x-b.x);
    double doi = (a.y - b.y ); 
    return unu * unu + doi * doi; 
}
bool angular_sort( Punct a, Punct b )
{
    double unu = angle( minim, a ); 
    double doi = angle( minim, b ); 
    if ( unu == doi ){
        return distanta( minim, a ) < distanta( minim, b );
    } else {
        return unu < doi; 
    }
    
}
/*
 * 
 */
int main(int argc, char** argv) {

    ifstream input("infasuratoare.in");
    ofstream output("infasuratoare.out");

    vector<Punct> puncte; 
    int n; 
    input >> n; 
    for ( int i=0; i<n; i++ ){
        double x,y; 
        input >> x >> y; 
        puncte.push_back( Punct(x,y) );
    }
    
    minim = Punct( puncte[0].x, puncte[0].y );
    for ( int i=1; i<n; i++ ){
        if ( minim.x > puncte[i].x || ( minim.x == puncte[i].x && minim.y > puncte[i].y ) ){
            minim = puncte[i]; 
        } 
    }
    
    //minim.print(); 
    sort( puncte.begin(), puncte.end(), angular_sort );
    
    //for ( int i=0; i<puncte.size(); i++ ){
      //  cout << "\n";
       // puncte[i].print(); 
     //   cout << " " << angle( minim, puncte[i] ) << "\n" ;
    //}
    
    vector<Punct> stack; 
    stack.push_back( minim );
    for ( int i=0; i<puncte.size(); i++ ){
        if ( puncte[i].x == minim.x && puncte[i].y == minim.y ){
        } else {
            while ( true ){
                if ( stack.size() <= 2 ){
                    stack.push_back( puncte[i] ); 
                    break;
                } else {
                    int s = stack.size(); 
                    if ( area(stack[s-2], stack[s-1], puncte[i] ) >= 0 ){
                        stack.push_back( puncte[i] );
                        break;
                    } else {
                        stack.pop_back();
                    }
                }
            }
            
        }
    }
    output.precision( 16 );
    output << stack.size() << "\n";
    for ( int i=0; i<stack.size(); i++){
        output << stack[i].x << " " << stack[i].y << "\n";
    }
    
    return 0;
}