Cod sursa(job #3224702)

Utilizator ninja_legend_11Vlad Marin-Perianu ninja_legend_11 Data 15 aprilie 2024 20:32:14
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define MAX 100000

using namespace std;

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

int64_t n, i, k, cmin, m=1;
struct coord{int64_t x, y;};
coord v[MAX];
stack<coord> s, r;

coord nextToTop()
{
    coord p = s.top();
    s.pop();
    coord res = s.top();
    s.push(p);
    return res;
}

int64_t dist(coord p1, coord p2)
{
    const int64_t o1=(p1.x-p2.x), o2=(p1.y-p2.y);
    return o1*o1+o2*o2;
}

int64_t orientatie(coord p1, coord p2, coord p3)
{
    int64_t val = (p2.y-p1.y)*(p3.x-p2.x)-(p3.y-p2.y)*(p2.x-p1.x);
    if(val == 0) return 0;
    else return (val > 0 ? 1 : 2);
}

bool compare(const coord i1, const coord i2)
{
    const int64_t o = orientatie(v[0], i1, i2);
    if(!o) return (dist(v[0], i2) >= dist(v[0], i1));
    else return (o == 2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    fin >> n >> v[0].x >> v[0].y;
    for(i=1; i < n; i++)
    {
        fin >> v[i].x >> v[i].y;
        if((v[i].y < v[cmin].y) || ((v[i].y == v[cmin].y) && (v[i].x < v[cmin].x))) cmin = i;
    }
    swap(v[0], v[cmin]);
    sort(v+1, v+n, compare);
    for(i=1; i < n; i++)
    {
        while((i < n-1) && (!orientatie(v[0], v[i], v[i+1]))) i++;
        v[m++] = v[i];
    }
    s.push(v[0]);
    s.push(v[1]);
    s.push(v[2]);
    for(i=3; i < m; i++)
    {
        while(s.size() > 1 && orientatie(nextToTop(), s.top(), v[i]) != 2) s.pop();
        s.push(v[i]);
    }
    while(!s.empty())
    {
        r.push(s.top());
        s.pop();
    }
    fout << r.size() << '\n';
    while(!r.empty())
    {
        fout << r.top().x << ' ' << r.top().y << '\n';
        r.pop();
    }
}