Cod sursa(job #3246676)

Utilizator Torna3oVirtopeanu Andrei Torna3o Data 3 octombrie 2024 22:57:22
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.61 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <stack>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct ura
{
    double x, y;
} v[120001];
int s[120001];


bool cmp(ura a, ura b)
{
    /// a < b == 1
    if(a.x < b.x)
    {
        return true;
    }
    else if(a.x > b.x)
    {
        return false;
    }
    else
    {
        if(a.y < b.y)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}

long long arie(ura a, ura b, ura c)
{
    return (a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x);
}



int main()
{
    int n, i, s_size = 1, cnt = 0, mic, mare;
    in >> n;
    for(i = 1; i <= n; i++)
    {
        in >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1, cmp);
    mic = 1;
    mare = n;
    s[1] = 1;
    for(i = 2; i <= n - 1; i++)
    {
        if(arie(v[mic], v[mare], v[i]) < 0) /// sub dreapta
        {
            if(arie(v[s[s_size]], v[mare], v[i]) < 0)
            {
                while(s_size > 1 && arie(v[s[s_size - 1]], v[s[s_size]], v[i]) < 0)
                {
                    s_size--;
                }
                s[++s_size] = i;
            }
        }
    }
    for(i = 1; i <= s_size; i++)
    {
       // cout << s[i] << " ";
    }
    s[++s_size] = n;
    int min_size = s_size;
    for(i = n - 1; i >= 1; i--)
    {
        if(arie(v[mic], v[mare], v[i]) > 0) /// deasupra dreptei
        {
            if(arie(v[mic], v[s[s_size]], v[i]) > 0)
            {
                while(s_size > min_size && arie(v[s[s_size]], v[s[s_size - 1]], v[i]) > 0)
                {
                    s_size--;
                }
                s[++s_size] = i;
            }
        }
    }
    s[++s_size] = 1;
    out << s_size - 1 << "\n";
    for(i = 2; i <= s_size; i++)
    {
        out << fixed << setprecision(6) << v[s[i]].x << " " << v[s[i]].y << "\n";
    }
//    out << s_size - 2 << "\n";
//    for(i = 3; i <= min_size; i++)
//    {
//        out << fixed << setprecision(6) << v[s[i]].x << " " << v[s[i]].y << "\n";
//    }
//    out << fixed << setprecision(6) << v[s[min_size + 2]].x << " " << v[s[min_size + 2]].y << "\n"; /// cel mai din dr
//    for(i = min_size + 3; i <= s_size; i++)
//    {
//        out << fixed << setprecision(6) << v[s[i]].x << " " << v[s[i]].y << "\n";
//    }
//    out << fixed << setprecision(6) << v[s[min_size + 1]].x << " " << v[s[min_size + 1]].y << "\n"; /// cel mai din st


    return 0;
}