Cod sursa(job #1091631)

Utilizator lilian_ciobanuLilian Ciobanu lilian_ciobanu Data 25 ianuarie 2014 21:11:38
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<fstream>
#include<algorithm>
#include<deque>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct QQ{
    double x;
    double y;
    double p;
};

bool cmp1(QQ i, QQ j){
    if(i.x==j.x)
        return i.y<j.y;
    else
        return i.x<j.x;
}

bool cmp2(QQ i, QQ j){
    return i.p<j.p;
}

QQ a[100005];
deque<int> b;


int main(){
    int n,i,j,x1,y1,k,q,w;
    double m;

    f>>n;

    for(i=1; i<=n; ++i){
        f>>a[i].x>>a[i].y;
    }

    sort(a+1,a+n+1, cmp1);

    x1=a[1].x; y1=a[1].y;
    for(i=2; i<=n; ++i){
        a[i].p=(a[i].y-y1)/(a[i].x-x1);
    }

    sort(a+2, a+n+1,cmp2);

    a[n+1]=a[1];

    b.push_back(1);
    b.push_back(2);
    b.push_back(3);

    if(n>3){
    for(i=1; i<n-1; ++i){
        k=b[b.size()-3];
        q=b[b.size()-2];
        w=b.back();
        m=(a[q].y-a[k].y)*(a[w].x - a[q].x) - (a[w].y - a[q].y)*(a[q].x - a[k].x);

        if(m>0){
            b[b.size()-2]=b.back();
            b.pop_back();
            b.push_back(b.back()+1);
        }
        else{
            b.push_back(b.back()+1);
        }

    }

    b.pop_back();
    }

    g<<b.size()<<"\n";
    for(i=0; i<b.size(); ++i){
        g<<a[b[i]].x<<" "<<a[b[i]].y<<"\n";
    }

return 0;
}