Cod sursa(job #2917141)

Utilizator RamanujanNeacsu Mihnea Ramanujan Data 3 august 2022 15:22:05
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include<vector>
#include<iomanip>
#include<algorithm>
#define x first
#define y second
#define pdd pair<double, double>
#define PRECISION 12
const int MAXN=2*1e5;
using namespace std;
pair<double, double>a[MAXN];
pdd st[MAXN];///implementam stiva ca TDA pt ca e necesara functionalitate extra
double angle(pdd A, pdd B, pdd C){
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
bool cmp(pdd A, pdd B){
    return angle(a[0], A, B)<0;
}
void convexHull(int n, int&lg){
    st[0]=a[0];
    st[1]=a[1];
    int top=1;
    for(int i=2; i<n; i++){///fiecare scoate de pe stiva tot ce are unghi concav
        while(angle(st[top-1], st[top], a[i])>0&&top>2)
            top--;
        st[++top]=a[i];
    }
    lg=top;
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int main()
{
    int n; fin>>n;
    for(int i=0; i<n; i++){
        fin>>a[i].x>>a[i].y;
    }
    int head=0, leftPos=0;
    for(int i=1; i<n; i++){
        if(a[i].x<a[leftPos].x)
            leftPos=i;
    }
    swap(a[leftPos], a[0]);
    sort(a+1, a+n, cmp);
    convexHull(n, head);
    fout<<head+1<<"\n";
    for(int i=head; i>=0; i--){
        fout<<setprecision(PRECISION)<<st[i].first<<" "<<st[i].second<<"\n";
    }
    return 0;
}