Cod sursa(job #360950)

Utilizator csizMocanu Calin csiz Data 2 noiembrie 2009 22:42:03
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

struct punct{
    double x;
    double y;
};
bool good(punct& p1,punct& p2,punct& p3){
    if( ( (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x) )<0) return false;
    return true;
}
class comp{
    punct referinta;
    public:
    comp(punct X):referinta(X){}
    bool operator()(const punct& p1,const punct& p2){
        return ( (p1.x-referinta.x)/(p1.y-referinta.y) > (p2.x-referinta.x)/(p2.y-referinta.y) );
    }
};


int main(){
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");
    int n;
    in>>n;
    vector<punct> v(n);
    int min=0;
    for(int i=0;i<n;i++){
        in>>v[i].x>>v[i].y;
        if(v[i].y>v[min].y){
            min=i;
        }
    }
    vector<punct> s;
    s.push_back(v[min]);
    comp comparatie(v[min]);
    v.erase(v.begin()+min);
    sort(v.begin(),v.end(),comparatie);
    s.push_back(v[0]);
    for(int i=1;i<v.size();i++){
        while(!good(s[s.size()-2],s[s.size()-1],v[i])){
            s.pop_back();
        }
        s.push_back(v[i]);
    }
    out<<s.size()<<endl;
    int primu=0;
    for(int i=0;i<s.size();i++){
        if(s[i].y/s[i].x<s[primu].y/s[primu].x) primu=i;
    }
    for(int i=primu;i<s.size();i++){
        out<<s[i].x<<" "<<s[i].y<<endl;
    }
    for(int i=0;i<primu;i++){
        out<<s[i].x<<" "<<s[i].y<<endl;
    }



}