Cod sursa(job #2703367)

Utilizator Katherine456719Swan Katherine Katherine456719 Data 8 februarie 2021 13:57:51
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

vector <pair<double,double> > v;
pair <double,double> point[120005];
int n;
double px, py;

double dist(double x1, double y1, double x2, double y2)
{
    double d2 = abs(x1-x2) * abs(x1-x2) + abs(x1-x2) * abs(x1-x2);
    return d2;
}

double det(double x1, double y1, double x2, double y2, double x3, double y3)
{
    return (x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3);
}

int cmp(pair <double,double> a,pair <double,double> b)
{
    if(det(px,py,a.first,a.second,b.first,b.second)>0)
        return a > b;
    if(det(px,py,a.first,a.second,b.first,b.second)<0)
        return a < b;
    if(det(px,py,a.first,a.second,b.first,b.second) == 0)
        if (dist(px, py, a.first, a.second) > dist(px, py, b.first, b.second))
            return a < b;
    return a > b;
}


int main() {

    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> point[i].first >> point[i].second;

    sort(point + 1,point + n + 1);
    px = point[1].first;
    py = point[1].second;
    sort(point + 2,point + n + 1,cmp);
    point[n + 1] = {px, py};
   for(int i = 1;i <= n + 1; ++i)
    {
        while (v.size() > 2 and det(v[v.size() - 2].first, v[v.size() - 2].second, v[v.size() - 1].first, v[v.size() - 1].second, point[i].first, point[i].second) < 0)
            v.pop_back();
        v.push_back({point[i].first, point[i].second});
    }
    v.pop_back();
    fout << v.size() << "\n";
    for (int i = 1; i < v.size()+1; ++i)
        fout << setprecision(6) << fixed << v[i].first << " " << setprecision(6) << fixed << v[i].second << "\n";
    return 0;
}