Cod sursa(job #2723337)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 13 martie 2021 22:00:15
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstdlib>

using namespace std;

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

const double INF = 2000000000.0;
const int NMAX = 120005;

struct point
{
    double x,y;
    point(){}
    point(int x,int y)
    {
        this->x = x;
        this->y = y;
    }
    bool operator==(const point &other) const{
    return ((x == other.x) && (y == other.y));
    }
    bool operator<(const point &other) const{
    return ((y*other.x) < (x*other.y));
    }
};

int semn(point a,point b,point c)
{
    double val = (a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x);
    if(val >= 0) return 1;
    return -1;
}

int n;
vector<point>p;
point st[NMAX];
int top = 0;
point LL;

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);fout.tie(0);
    LL.x = INF;
    LL.y = INF;
    fin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        point temp;
        fin >> temp.x >> temp.y;
        p.push_back(temp);
        if(LL.y > temp.y)
        {
            LL.x = temp.x;
            LL.y = temp.y;
        }
        else if(LL.y == temp.y && LL.x > temp.x)
            LL.x = temp.x;
    }
    for(int i = 1 ; i < p.size() ; i++)
        {
            if(p[i] == LL)
                swap(p[0],p[i]);
            p[i].x -= LL.x;
            p[i].y -= LL.y;
        }
    p[0] = point({0,0});
    sort(p.begin()+1,p.end());
    st[++top] = p[0];
    st[++top] = p[1];
    st[++top] = p[2];
    for(int i = 3 ; i < p.size() ; i++)
    {
        while(top >= 2 && semn(st[top-2],st[top-1],st[top]) != semn(st[top-1],st[top],p[i]))
            top--;
        st[++top] = p[i];
    }
    fout << top << '\n';
    for(int i = 1 ; i <= top ; i++)
        fout << fixed << setprecision(6) << st[i].x + LL.x << ' ' << st[i].y + LL.y << '\n';
    return 0;
}