Cod sursa(job #1892542)

Utilizator markyDaniel marky Data 25 februarie 2017 02:37:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
//#include<iomanip>

using namespace std;
typedef pair <double,double> p;
int n;
vector <p> a;
class stack
{
public:
    vector <p> st;
    void pb(p x)
    {
        st.push_back(x);
    }
    void pop()
    {
        st.pop_back();
    }
    p last()
    {
        return st.back();
    }
    p last2()
    {
        return st[st.size()-2];
    }
    void Print()
    {
        printf("%d\n",(int)st.size());
        for(int i=0;i<(int)st.size();i++)
            printf("%lf %lf\n",st[i].first,st[i].second);
    }
};
bool cmp(p x,p y)
{
    return (y.first-a.begin()->first)*(x.second-a.begin()->second)<(x.first-a.begin()->first)*(y.second-a.begin()->second);
}
double prod(p x,p y,p z)
{
    return  (z.first-x.first)*(y.second-x.second)-(y.first-x.first)*(z.second-x.second);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        p x;
        scanf("%lf%lf",&x.first,&x.second);
        a.push_back(x);
    }
    vector <p> ::iterator it =a.begin()+1,min=a.begin();
    for(;it!=a.end();it++)
        if(it->first<min->first||it->first==min->first&&it->second<min->second)
            min=it;
    swap(*a.begin(),*min);
    stable_sort(a.begin()+1,a.end(),cmp);
    stack st;
    st.pb(*a.begin());st.pb(*(a.begin()+1));st.pb(*(a.begin()+2));
    it=a.begin()+3;
    while(it!=a.end())
    {
        while(prod(st.last2(),st.last(),*it)>=0)
            st.pop();
        st.pb(*it++);
    }
    //printf("%d",fixed);
    st.Print();
    return 0;
}