Cod sursa(job #2703626)

Utilizator Katherine456719Swan Katherine Katherine456719 Data 8 februarie 2021 20:40:34
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 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 true;
    if(det(px,py,a.first,a.second,b.first,b.second)<0)
        return false;
    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 false;
    return true;
}


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;
    point[n + 1] = {px, py};
    sort(point + 2,point + n + 1,cmp);
    v.push_back(point[1]);
   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.back().first, v.back().second, point[i].first, point[i].second) <= 0)
            v.pop_back();
        v.push_back(point[i]);
    }
    v.pop_back();
    fout << v.size() << "\n";
    for (int i = 0; i < v.size(); ++i)
        fout << setprecision(6) << fixed << v[i].first << " " << setprecision(6) << fixed << v[i].second << "\n";

    return 0;
}