Cod sursa(job #2099073)

Utilizator edynator34Nechitoaia George-Edward edynator34 Data 3 ianuarie 2018 22:25:33
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include<fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
long double x,y;
int i,n;
pair <long double, long double> v[120001];
vector<pair <long double, long double> > sol;
long double determinant (long double x_1, long double y_1, long double x_2, long double y_2, long double x_3, long double y_3 )
{
    return x_1*y_2+x_2*y_3+x_3*y_1-y_1*x_2-y_2*x_3-y_3*x_1;
}

bool cmp ( const pair <long double, long double> a, const pair <long double, long double> b)
{
    if ( determinant(v[0].first, v[0].second, a.first, a.second, b.first, b.second) < 0) return false;
    return true;
}

int main()
{
    in>>n;
    for(i=0;i<n;i++){
        in>>v[i].first>>v[i].second;
        if ( v[i].first<v[0].first || (v[i].first == v[0].first && v[i].second < v[0].second)) swap (v[0], v[i]);
    }
     sort (v+1, v+n, cmp );
   /// cout<<v[1].first<<' '<<v[1].second;
   for ( int i = 0; i < n; ++i )
    {
        bool adevarat = true;
        while ( sol.size() >= 2 && adevarat )
        {
            adevarat = false;
            pair < long double, long double > a = sol.back();
            sol.pop_back();
            if ( determinant(sol.back().first, sol.back().second, a.first, a.second, v[i].first, v[i].second) <= 0 ) adevarat = true;
            else sol.push_back(a);
        }
        sol.push_back(v[i]);
    }
       out<<sol.size()<<'\n';
    for ( int i = 1; i < sol.size(); ++i ) out<<fixed<<setprecision(6)<<sol[i].first<<" "<<sol[i].second<<'\n';
    out<<fixed<<setprecision(6)<<sol[0].first<<" "<<sol[0].second<<'\n';
    return 0;
}