Cod sursa(job #2702792)

Utilizator Katherine456719Swan Katherine Katherine456719 Data 5 februarie 2021 21:17:11
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.91 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 tgp(double x1, double y1, double x2, double y2)
{
    double r;
    if(x1==x2)
        r= 99999999;
    else
        r = (y2-y1)/(x2-x1);
    return r;
}

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;
}


int cmp(pair <double,double> a,pair <double,double> b)
{
    double tg1 = tgp(a.first,a.second,px,py) ,tg2 = tgp(b.first,b.second,px,py);
    if(tg1 > tg2)
        return a < b;
    else {
        if (tg1 == tg2) {
            if (dist(a.first, a.second, px, py) > dist(b.first, b.second, px, py))
                return a < b;
            else
                return a > b;
        }
        else
            return a > b;
        }
}

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

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);
    int k = 2;
    while(k <= n)
    {
        if(v.size() == 0)
        {
            v.push_back({point[k].first,point[k].second});
            k++;
        }
        else {
            if(v.size() == 1 && det(px, py, v[v.size() - 1].first, v[v.size() - 1].second,point[k].first, point[k].second) >= 0)
            {
                v.push_back({point[k].first, point[k].second});
                k++;
            }
            else
            {
                if (v.size() > 1 && det(v[v.size() - 2].first, v[v.size() - 2].second, v[v.size() - 1].first, v[v.size() - 1].second,point[k].first, point[k].second) >= 0) {
                    v.push_back({point[k].first, point[k].second});
                    k++;
                } else {
                    if (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[k].first, point[k].second) < 0) {
                        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[k].first, point[k].second) < 0) {
                            v.pop_back();
                            v.push_back({point[k].first, point[k].second});
                            k++;
                        }
                    } else k++;

                }
            }
        }
    }
    fout << v.size() + 1 << "\n";
    for (int i = 0; i < v.size(); ++i)
        fout << setprecision(6) << fixed << v[i].first << " " << setprecision(6) << fixed << v[i].second << "\n";
    fout << setprecision(6) << fixed << px << " " << setprecision(6) << py << "\n";
    return 0;
}