Cod sursa(job #1370512)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 3 martie 2015 15:17:48
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define s sol.size()

using namespace std;

vector <pair<double, double> >li;
int n;
double a, b, x=1000006, y=1000006;
vector <int> sol;

double area(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
    return a.x*b.y + b.x*c.y + a.y*c.x - c.x*b.y - b.x*a.y - a.x*c.y;
}

class compare
{
public:
    bool operator()(const pair<double, double> &a, const pair<double, double> &b)
    {
        pair <double, double> p;
        p.x=x;
        p.y=y;
        if(a!=p && b!=p)
            return (a.y-y)/(a.x-x) > (b.y-y)/(b.x-x);
        else if(a==p) return true;
        else return false;
    }
};

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    cin>>n;

    for(int i=1; i<=n; i++)
    {
        cin>>a>>b;
        li.pb({a, b});
        if(x>a)
        x=a,y=b;
        if(x==a && y<b)
        y=b;
    }

    sort(li.begin(), li.end(), compare());

    sol.pb(0);
    sol.pb(1);
    for(int i=2;i<n;i++)
    {
        if(area(li[sol[s-2]], li[sol[s-1]], li[i])>0)
                sol.pop_back();

        sol.pb(i);
    }
    cout<<s<<'\n';
    for(int i=s-1;i>=0;i--)
    {
        printf("%.12f %.12f\n", li[sol[i]].x,li[sol[i]].y);
    }


    return 0;
}