Cod sursa(job #3213767)

Utilizator and_Turcu Andrei and_ Data 13 martie 2024 13:52:31
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.97 kb
//
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("infasuratoare.in");
//ofstream fout("infasuratoare.out");
//
//struct Punct
//{
//    double x, y;
//    bool operator < (const Punct alt) const
//    {
//        if (alt.y == y)
//            return x < alt.x;
//        return y < alt.y;
//    }
//};
//Punct a[120003];
//int n;
//bool viz[120005];
//int st[120005], top;
//
//double F(Punct A, Punct B, Punct C)
//{
//    return (A.y - B.y) * C.x + (B.x - A.x) * C.y
//        + A.x * B.y - A.y * B.x;
//}
//
//int main()
//{
//    fin >> n;
//    int i;
//    for (i = 1; i <= n; i++)
//        fin >> a[i].x >> a[i].y;
//
//    sort(a + 1, a + n + 1);
//cout << a[n].x << " " << a[n].y ;
//    st[++top] = 1;
//    st[++top] = 2;
//    viz[2] = 1;
//    for (i = 3; i <= n; i++)
//    {
//        while (top >= 2 and F(a[st[top - 1]], a[st[top]], a[i]) <= 0)
//        {
//            viz[st[top]] = 0;
//            top--;
//        }
//        st[++top] = i;
//        viz[i] = 1;
//    }
//
//    for (i = n; i >= 1; i--)
//    {
//        if (viz[i] == 0)
//        {
//            while (top >= 2 and F(a[st[top - 1]], a[st[top]], a[i]) <= 0)
//                top--;
//            st[++top] = i;
//        }
//    }
//    fout << top - 1 << "\n";
//    for (int i = 1; i < top; i++)
//        fout << setprecision(12) << fixed << a[st[i]].x << " " << a[st[i]].y << "\n";
//
//
//    return 0;
//}



#include <bits/stdc++.h>
#define N 120007
using namespace std;

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

#define int double
vector<pair<int,int>>a;
int32_t n;
int32_t st[N];
bool viz[N];
int32_t top;

//inline bool Determinant( pair<int,int>x,pair<int,int>y,pair<int,int>z )
//{
//    return (y.first*z.second -x.first*z.second
//            -y.first*x.second -z.first*y.second
//            +z.first*x.second +x.first*y.second)<=0;
//}
inline bool Determinant(pair<int,int> A, pair<int,int> B, pair<int,int> C)
{
    return ( (A.second - B.second) * C.first + (B.first- A.first) * C.second
        + A.first * B.second - A.second* B.first )<=0;
}

int32_t main()
{
    fin >> n;
    for(int i=1;i<=n;i++)
    {
        pair<int,int>aux;
        fin >> aux.second >> aux.first ;
        a.push_back(aux);
    }
    sort(a.begin(),a.end());
    for(int i=0;i<n;i++)
        swap( a[i].first,a[i].second );

    st[top]=0;
    st[++top]=1;
    viz[0]=1;
    viz[1]=1;

    /// index 0
    for(int32_t i=2;i<n;i++)
    {
        while( top>=1 and Determinant(a[st[top-1]],a[st[top]],a[i]) )
        {
            viz[ st[top] ]=0;
            top--;
        }
        st[++top]=i;
        viz[i]=1;
    }
    for(int32_t i=n-1;i>=0;i--)
        if( !viz[i] )
        {
            while( top>=1 and Determinant(a[st[top-1]],a[st[top]],a[i]) )
                top--;
            st[++top]=i;
        }

    fout << top+1 <<"\n";
    for(int i=0;i<=top;i++)
        fout << setprecision(12) << fixed  << a[i].first << " " << a[i].second << "\n";
    return 0;
}