Cod sursa(job #2270034)

Utilizator slym777Darii Dan slym777 Data 26 octombrie 2018 23:38:50
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <bits/stdc++.h>
#define pdd pair <double, double>
#define Nmax 120010
#define mp make_pair

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
pdd points[Nmax];
vector < pdd > L;

double orientation(pdd q,pdd p,pdd r)
{
    return (r.second - q.second) * (p.first - q.first) - (r.first - q.first) * (p.second - q.second);
}


bool cmp(pdd a,pdd b)
{
    return orientation(points[1],a,b) > 0;
}

void sortare()
{
    int pr = 1;
    for (int i = 2; i <= n; i++)
        if (points[i] < points[pr])
            pr = i;
    swap(points[1],points[pr]);
    sort(points + 2, points + n + 1, cmp);
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> points[i].first >> points[i].second;
   /* for (int i = 1; i<=n; i++)
        cout << points[i].first << " " << points[i].second << "\n";
    cout << endl;*/
    sortare();
    /*for (int i = 1; i<=n; i++)
        cout << points[i].first << " " << points[i].second << "\n";
    cout << endl;*/
    L.push_back(points[1]);
    L.push_back(points[2]);
    for (int i = 3; i <= n; i++)
    {//cout << orientation(L[L.size()-2],L[L.size()-1],points[i]) << " " << points[i].first << " " << points[i].second << "\n";
        while (L.size() > 2 && orientation(L[L.size()-2],L[L.size()-1],points[i]) <= 0)
            L.pop_back();
        L.push_back(points[i]);
        /*for(auto a:L)
      cout << a.first << ", " << a.second << "\n";
      cout << "\n";*/
    }
    fout << L.size() << "\n";
    fout << setprecision(9) << fixed;
    for(auto a:L)
      fout << a.first << " " << a.second << "\n";

    return 0;
}