Cod sursa(job #2712465)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 25 februarie 2021 19:44:48
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <bits/stdc++.h>
#define inf 1000999090

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct punct
{
     long double x,y;
}v[120100],s[120100];

int compare(punct A, punct B)
{
    /// m1 = (A.x-v[1].x) / (A.y-v[1].y) -> panta lui A fata de primul punct
    /// m2 = (B.x-v[1].x) / (B.y-v[1].y) -> panta lui A fata de primul punct
    /// corect este return(m1>m2)
    /// dar nu comparam rapoarte, ci produse pe diagonala

    return ((A.x - v[1].x) * (B.y - v[1].y) > (A.y-v[1].y) * (B.x - v[1].x));
}

int viraj_dreapta(punct A, punct B, punct C)
{
    /// se face determinant:
    /// A.x A.y 1
    /// B.x B.y 1
    /// C.x C.y 1

    /// daca valoarea este negativa sau egala cu 0 => viraj dreapta
    /// asa e formula - o iei ca atare
    /// e putin tricky atunci cand determinantul este 0 => punctele sunt coliniare
    /// pot aparea prob. in cazul asta
    /// dar ni se garanteaza ca nu vor exista puncte coliniare in aceasta problema
    return((A.x*B.y + B.x*C.y + A.y*C.x - B.y*C.x - C.y*A.x - A.y*B.x) <= 0);
}

int n,i,minix=inf,miniy=inf,poz,T;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;
        if(v[i].x<minix)
        {
            minix=v[i].x;
            miniy=v[i].y;
            poz=i;
        }
        else if(v[i].x==minix)
        {
            if(v[i].y<miniy)
            {
                miniy=v[i].y;
                poz=i;
            }
        }
    }

    swap(v[1],v[poz]);
    sort(v+2,v+n+1,compare);

    /// punem in stiva primele doua puncte
    s[1]=v[1];
    s[2]=v[2];
    T=2;

    for(i=3;i<=n;i++)
    {
        /// eliminam cat putem (trb. totusi sa avem minim 2 puncte) si cat timp obtinem "viraj" la dreapta
        /// in viraj_dreapta() conteaza ordinea -> pentru ca noi comparam punctul curent cu un vector, unde este important si sensul
        while(T>2 && viraj_dreapta(s[T-1],s[T],v[i]))T--;

        T++;
        s[T]=v[i];
    }

    g<<T<<'\n';
    for(i=1;i<=T;i++)
        g<<fixed<<setprecision(12)<<v[i].x<<" "<<fixed<<setprecision(12)<<v[i].y<<'\n';
    return 0;
}