Cod sursa(job #3215422)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 14 martie 2024 22:15:30
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Punct
{
    float x , y;
}a[120001];

vector <Punct> hull;
int N;

float up (Punct X)
{
    return acos((1.0 * X.x) / sqrt(X.x * X.x + X.y * X.y));
}

bool cmp (Punct A , Punct B)
{
    return up (A) < up (B);
}

int Orientation (Punct A , Punct B , Punct C)
{
    float t = (B.y - A.y) * (C.x - B.x) - (C.y - B.y) * (B.x - A.x);
    if(t == 0)
        return 0;       /// Coliniare
    else if(t > 0)
        return 1;       /// inv. trig
    return 2;
}

int main()
{
    fin >> N;
    for (int i = 1; i <= N; ++i)
        fin >> a[i].x >> a[i].y;
    /// Aleg punctul cu ordonata minima
    int p = 1;
    for (int i = 2; i <= N; ++i)
        if(a[i].x < a[p].x || (a[i].x == a[p].x && a[i].y < a[p].y))
            p = i;
    /// Realizez infasurarea
    int currInd = p;
    do
    {
        hull.push_back(a[currInd]);
        int ind;
        if(currInd == N)
            ind = 1;
        else
            ind = currInd + 1;
        for (int i = 1; i <= N; ++i)
            if(Orientation(a[currInd] , a[i] , a[ind]) == 2)    /// Punctul i realiz. o intoarecere mai mare
                ind = i;
        currInd = ind;
    }while(currInd != p);
    fout << fixed << setprecision(12);
    fout << hull.size() << "\n";
    sort (hull.begin() , hull.end() , cmp);
    for (int i = 0;  i < hull.size(); ++i)
        fout << hull[i].x << " " << hull[i].y << "\n";
}