Cod sursa(job #1501714)

Utilizator zertixMaradin Octavian zertix Data 13 octombrie 2015 19:27:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

int n;
pair<double, double > P[120020];
///sortam dupa valoarea determinantului
/// luam primul punct fix si dupa daca det(a,b,c)<0 ->b<c

vector < int >v;

double det(pair < double ,double > a, pair < double,double > b,pair < double,double > c)
{
    return (b.first-a.first)*(c.second-a.second)-(c.first-a.first)*(b.second-a.second);
}
struct cmp
{
    bool operator ()(pair <const double ,const double > a, pair <const double,const double> b)
    {
        return det(P[1],a,b)>0;
    }
};

void citire ()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d", &n);

    for (int i=1;i<=n;++i)
        scanf("%lf%lf",&P[i].first,&P[i].second);
}

void infasuratoare()
{

    int p=1,i;

    for (i=2; i<=n; ++i)
        if (P[i] < P[p])
            p=i;

    swap(P[1],P[p]);

    sort(P+2,P+n+1,cmp());
    v.push_back(1);
    v.push_back(2);

    for (i=3;i<=n;++i)
    {
        int siz=v.size();
        while (siz>=2 && det (P[v[siz-2]],P[v[siz-1]],P[i])<0)
        {
            --siz;
            v.pop_back();
        }
        v.push_back(i);
    }
    printf("%d\n",v.size ());
    for (int i=0;i<v.size();++i)
    printf("%lf %lf\n",P[v[i]].first,P[v[i]].second);
}

int main()
{
    citire();
    infasuratoare();
    return 0;
}