Cod sursa(job #1368280)

Utilizator AeroHHorea Stefan AeroH Data 2 martie 2015 15:53:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define punct pair<double,double>
#define x first
#define y second
using namespace std;

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

int N,i,j;

vector<punct> v;

bool ec(punct a,punct b,punct c)
    {
        double A=a.y - b.y;
        double B=b.x - a.x;
        double C=b.y * a.x - a.y * b.x;
        return (A * c.x + B * c.y + C > 0);
    }

double a,b;

int main()
{

    f>>N;
    for(i=1;i<=N;++i)
    {
        f>>a>>b;
        v.push_back(make_pair(a,b));
    }
    sort(v.begin(),v.end());

    vector<punct> st,hull;

    st.push_back(v[0]);
    for(i=1;i<N;++i)
    {
        if(ec(v[0],v[N-1],v[i]) || i == N - 1)
            {
            while(st.size()>=2 && !ec(st[st.size()-2],v[i],st.back()))
                st.pop_back();
            st.push_back(v[i]);
            }
    }
    hull=st;hull.pop_back();
    st.clear();

    st.push_back(v[N-1]);
    for(i=N-1;i>=0;--i)
    {
        if(ec(v[N-1],v[0],v[i]) || i == 0)
            {
            while(st.size()>=2 && !ec(st[st.size()-2],v[i],st.back()))
                st.pop_back();
            st.push_back(v[i]);
            }
    }

    for(i=0;i<st.size();++i)
        hull.push_back(st[i]);

    g<<hull.size()-1<<'\n';
    for (i=hull.size()-2;i>=0;--i)
            g<<fixed<<setprecision(6)<<hull[i].first<<" "<<hull[i].second<<'\n';


    return 0;
}