Cod sursa(job #3222532)

Utilizator dragutamihai1234Draguta Mihai dragutamihai1234 Data 10 aprilie 2024 18:35:59
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.88 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#include <iomanip>
using namespace std;

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

struct puncte
{
    double x, y;
};
puncte v[130001];
vector <puncte>st;


bool comp(puncte a, puncte b)
{
    double x = v[1].x,
           y = v[1].y;
    return (a.y - y) * (b.x - x) < (a.x - x) * (b.y - y);
}

double determinant(puncte a, puncte b)
{
    return a.x * b.y - b.x * a.y;
}

int orientare(puncte a, puncte b, puncte c)
{
    double ras = determinant(a, b) + determinant(b, c) + determinant(c, a);
    if(ras > 0)
        return 1;
    if(ras < 0)
        return -1;
    return 0;
}

int main()
{
    int n;
    f >> n;
    for(int i = 1; i <= n; i++)
    {
        f >> v[i].x >> v[i].y;
        if(v[i].y < v[1].y)
            swap(v[1], v[i]);
    }
    sort(v + 2, v + n + 1, comp);
    st.push_back(v[1]);
    st.push_back(v[2]);
    for(int i = 3; i <= n; i++)
    {
        while(st.size() >= 2 && orientare(st[st.size() - 2], st[st.size() - 1], v[i]) != 1)
            st.pop_back();
        st.push_back(v[i]);
    }
    g << st.size() << '\n';
    for(int i = 0; i < st.size(); i++)
    {
        g << fixed << setprecision(6) << st[i].x << ' ' << st[i].y << '\n';
    }
    return 0;
}



























/*
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

struct nume
{
    double x, y;
};

nume v[120001];

double minx = 1e9, miny = 1e9;
vector <nume>st;

bool comp(nume a, nume b)
{
    return (-minx + a.x) * (-miny + b.y) > (-miny + a.y) * (-minx + b.x);
}

double determinant(nume a, nume b)
{
    return a.x * b.y - a.y * b.x;
}

int orientare(nume a, nume b, nume c)
{
    double val = determinant(a, b) + determinant(b, c) + determinant(c, a);
    if(val > 0)
        return 1;
    else
        if(val == 0)
            return 2;
        else
            return 3;
}

int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    ///
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i].x >> v[i].y;
        if(v[i].y < miny)
        {
            miny = v[i].y;
            minx = v[i].x;
            swap(v[1], v[i]);
        }
    }
    sort(v + 2, v + n + 1, comp);
    st.push_back(v[1]);
    st.push_back(v[2]);
    for(int i = 3; i <= n; i++)
    {
        while(st.size() > 1 && orientare(st[st.size() - 2], st[st.size() - 1], v[i]) != 1)
            st.pop_back();
        st.push_back(v[i]);
    }
    cout << st.size() << '\n';
    for(int i = 0; i < st.size(); i++)
    {
        cout << fixed << setprecision(6) << st[i].x << ' ' << st[i].y << '\n';
    }
    return 0;
}
*/