Cod sursa(job #3001856)

Utilizator robertanechita1Roberta Nechita robertanechita1 Data 13 martie 2023 23:04:12
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, top, st[120005], viz[120005];
vector<int>ans;
struct Elem{
    double x, y;
    bool operator < (const Elem A) const{
        if(y == A.y)
            return  x < A.x;
        return y <  A.y;
    }
}a[120005];

long double Dreapta(Elem C, Elem A, Elem B){
    ///y-yA/yB-yA = x-xA/xB-xA
    long double a = B.y - A.y;
    long double b = A.x - B.x;
    long double c = A.x * (A.y - B.y) + A.y * (B.x - A.x);
    return a * C.x + b * C.y + c;
}

void ConvexHull(){
    st[1] = 1;
    top = 1;
    for(int i = 2; i <= n; i++){
        while(top > 1&& Dreapta(a[i], a[st[top-1]], a[st[top]]) > 0){
            viz[st[top]] = 0;
            top--;
        }
        st[++top] = i;
        viz[i] = 1;
    }
    for(int i = 1; i <= top; i++)
        ans.push_back(st[i]);
    st[1] = n;
    top = 1;
    for(int i = n-1; i >= 1; i--)
        if(!viz[i]){
            while(top > 1&& Dreapta(a[i], a[st[top-1]], a[st[top]]) > 0){
                viz[st[top]] = 0;
                top--;
            }
            st[++top] = i;
            viz[i] = 1;
        }
    for(int i = 2; i < top; i++)
        ans.push_back(st[i]);
    fout << ans.size() << "\n";
    for(auto i : ans)
        fout << fixed << setprecision(12) << a[i].x << " " << a[i].y << "\n";
}

int main()
{
    fin >> n ;
    for(int i = 1; i <= n; i++)
        fin >> a[i].x >> a[i].y;
    ConvexHull();
    return 0;
}