Cod sursa(job #3159625)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 21 octombrie 2023 18:03:04
Problema Infasuratoare convexa Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct puncte
{
   double x, y;
};

puncte a[120005];
puncte b[120005];
///aici pun punctele finale
int k=0; ///nr de puncte ale poligonului convex
int n;

bool comparexpoints(puncte a1, puncte a2)
{
    if(a1.x==a2.x)
    {
        if(a1.y>a2.y)
            return 1;
        else return 0;
    }
    else if(a1.x<a2.x)
        return 1;
    return 0;
}

enum orientare{
       TRIGONOMETRIC,
       ORAR,
       COLIN
};

orientare calcOrientare(puncte p1, puncte p2, puncte p3)
{
    double det=(p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
    if(det<0)
        return TRIGONOMETRIC;
    else if(det>0)
        return ORAR;
    else
        return COLIN;
}

void parcurgereinfasuratorsus()
{

    for(int i=0; i<n; i++)
    {

            ///testez daca merge bagat punctul a[i]
           while(k>=2 && calcOrientare(b[k - 2], b[k - 1], a[i])!=ORAR)
                {
                    k--;
                }
            b[k++]=a[i];
    }
}

void parcurgereinfasuratorjos()
{

    for(int i=n-2; i>=0; i--)
    {

            ///testez daca merge bagat punctul a[i]
           while(k>=2 && calcOrientare(b[k - 2], b[k - 1], a[i])!=ORAR)
                {
                    k--;
                }
            b[k++]=a[i];
    }
}

int main()
{
    fin >> n;
    for(int i=0; i<n; i++)
        fin >> a[i].x >> a[i].y;
    sort(a, a+n, comparexpoints);
    parcurgereinfasuratorsus();
    parcurgereinfasuratorjos();
    k--;
    fout << k << "\n";
    for(int i=0; i<k; i++)
        fout << fixed << setprecision(6) << b[i].x << " " << b[i].y << '\n';
    return 0;
}