Cod sursa(job #3293368)

Utilizator Simon2712Simon Slanina Simon2712 Data 11 aprilie 2025 16:05:35
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{
    double x, y;
};
const int N = 12e4;

point p[N + 1];
int st[N + 1];
int n, sz;

double orientation(point a, point b, point c)
{
    return  (b.x - a.x) * (c.y - b.y) -
            (b.y - a.y) * (c.x - b.x);
}

double manhattan(point a, point b){
    return fabs(a.x - b.x) + fabs(a.y - b.y);
}


void convex_hull(){
    sz = 0;
    for(int i = 1; i <= n; i++)
    {
        while(sz > 2 && orientation(p[st[sz - 1]], p[st[sz]], p[i]) < 0)
            sz--;
        sz++;
        st[sz] = i;
    }
    while(sz > 3 && orientation(p[st[sz - 1]], p[st[sz]], p[1]) < 0)
        sz--;
}

void print_hull(){
    fout<<sz<<'\n';
    for(int i = 1; i <= sz; i++)
        fout<<p[st[i]].x<<' '<<p[st[i]].y<<'\n';
}


bool cmp(point a, point b)
{
    int orient = orientation(p[1], a, b);
    if(orient == 0) ///a, b, p[1] coliniare
        return manhattan(p[1], a) < manhattan(p[1], b); ///choose closer point
    return orient > 0; ///order points clockwise
}

void sort_points(){
    sort(p + 2, p + n + 1, cmp);
}

void find_lowest(){
    int ind = 1;
    for(int i = 2; i <= n; i++)
    {
        if(p[i].x < p[ind].x || (p[i].x == p[ind].x && p[i].y < p[ind].y))
            ind = i;
    }
    swap(p[ind], p[1]);///make first point be the lowest
}

void read(){
    fin>>n;
    for(int i = 1; i <= n; i++)
        fin>>p[i].x>>p[i].y;
}
int main()
{
    read();
    find_lowest();
    sort_points();
    convex_hull();
    print_hull();
    return 0;
}