Cod sursa(job #3195979)

Utilizator tbi1233Tiberiu Telcean tbi1233 Data 22 ianuarie 2024 13:33:43
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.48 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <stack>
#include <iomanip>

using namespace std;

#define F long double
const F eps = 1e-12;
ifstream fin("infasuratoareconvexa.in");
ofstream fout("infasuratoareconvexa.out");

bool isright(F x1, F y1, F x2, F y2, F x3, F y3)
{
    F s = (-(x3-x2))*((y2-y1))/((x1-x2));
    return ((s + y2 - y3) >= 0) ^ ((x1 - x2) >= 0);
}

F isRight(F x1, F y1, F x2, F y2, F x3, F y3)
{
    return ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1));
}

F dsq(F x1, F y1, F x2, F y2)
{
    return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}

struct c {F x; F y;
bool operator<(const struct c &other) const
{
    if(y == other.y)
        return x<other.x;
    return y<other.y;
}
};

F angle(c f, c s)
{
    return atan2(s.y-f.y, s.x-f.x);
}

bool iscolinear(c f, c s, c t)
{
    F g = (-(t.x-s.x))*((s.y-f.y))/((f.x-s.x));
    return abs(g + s.y - t.y) <= eps;
}

F cisright(c f, c s, c t)
{
    return (isRight(f.x, f.y, s.x, s.y, t.x, t.y));
}

template<typename T>
T peek(stack<T>& s)
{
    const T x = s.top();
    s.pop();
    const T y = s.top();
    s.push(x);
    return y;
}

void print(stack<c> s)
{
    while(!s.empty())
    {
        fout << s.top().x << " " << s.top().y << endl;
        s.pop();
    }
}

stack<c> convexhullr(vector<c> p)
{
    stack<c> s;
    s.push(p[0]);
    s.push(p[1]);
    for(int i=2; i<p.size(); i++) {
        while(s.size() >= 2 && cisright(peek(s), s.top(), p[i]) < 0)
            s.pop();
        s.push(p[i]);
    }
    return s;
}
stack<c> convexhulll(vector<c> p)
{
    stack<c> s;
    s.push(p[0]);
    s.push(p[1]);
    for(int i=2; i<p.size(); i++) {
        while(s.size() >= 2 && cisright(peek(s), s.top(), p[i]) > 0)
            s.pop();
        s.push(p[i]);
    }
    return s;
}

stack<c> rev(stack<c> a)
{
    stack<c> b;
    while(!a.empty())
    {
        b.push(a.top());
        a.pop();
    }
    return b;
}

int main()
{
    int k;
    fout << fixed;
    fout << setprecision(0);
    vector<c> a;
    fin >> k;
    for(int i=0; i<k; i++)
    {
        F x, y;
        fin >> x >> y;
        a.push_back((struct c){x,y});
    }
    sort(a.begin(), a.end());
    stack<c> s1 = rev(convexhullr(a));
    stack<c> s2 = convexhulll(a);
    s2.pop();
    s2=rev(s2);
    s2.pop();
    s2=rev(s2);
    fout << s1.size()+s2.size() << endl;
    print(s1);
    print(s2);
    return 0;
}