Cod sursa(job #2537734)

Utilizator AlexBolfaAlex Bolfa AlexBolfa Data 3 februarie 2020 22:02:26
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
#define NMAX (int)(2e5+4)
#define pb emplace_back
#define ft first
#define sd second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef pair <int, int> pairINT;
typedef long long ll;
struct point{
    double x,y;
    bool operator<(const point& oth)const{
        return (make_pair(x, y) < make_pair(oth.x, oth.y));
    }
};

point p[NMAX];
int n;
vector <int> stk;

bool TrigoOrder(point,point,point);
inline bool cond(point&,point&);

int main(){
    fin>>n;
    double x,y;
    for(int i=0;i<n;++i){
        fin>>x>>y;
        p[i]={x, y};
        if(p[i] < p[0])
            swap(p[i], p[0]);
    }
    //p[0] tine minimul
    sort(p+1,p+n,cond);
    stk.push_back(0);
    stk.push_back(1);

    for(int i=2;i<n;++i){
        while(!TrigoOrder(p[stk[stk.size()-2]], p[stk.back()], p[i]))
            stk.pop_back();
        stk.push_back(i);
    }
    fout<<fixed<<setprecision(12);
    fout<<stk.size()<<'\n';
    for(auto it:stk)
        fout<<p[it].x<<' '<<p[it].y<<'\n';
    return 0;
}
inline bool cond(point& A,point& B){
    return TrigoOrder(p[0], A, B);
}
bool TrigoOrder(point A,point B,point C){
    return ((C.y - A.y)*(B.x - A.x) - (B.y - A.y)*(C.x - A.x)) > 0.0;
}