Cod sursa(job #2979477)

Utilizator samyro14Samy Dragos samyro14 Data 15 februarie 2023 10:48:21
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
using namespace std;

#define ll unsigned long long
#define fast_read ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define INF 0x3f3f3f3f3f3f
#define x first
#define y second
const int maxn = 12e4;
const int maxm = 2e5;
const int mod = 666013;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, k;
typedef pair<double, double> Point;

Point a[maxn + 2], b[maxn + 2];
void read(){
   fin >> n;
   for(int i = 1; i <= n; ++i) fin >> a[i].x >> a[i].y;
}
int arie(Point& a, Point& b, Point& c){
    return (b.x - a.x) * (a.y - c.y) - (c.x - a.x) * (a.y - b.y);
}
bool cmp(Point a, Point b){
    return arie(b[1], a, b) < 0;
}
void convex_hull(){
    int pos = 1;
    for(int i = 2; i <= n; ++i)
        if(a[i] < a[pos])
            pos = i;
    swap(a[pos], a[1]);
    sort(a + 2, a + n + 1, cmp);
    b[++k] = a[1];
    b[++k] = a[2];
    for(int i = 3; i <= n; ++i){
        while(k >= 2 && (arie( b[k - 1], b[k], a[i]) > 0))
            k--;
        b[++k] = a[i];
    }
}
void write(){

    fout << k << "\n";
    for(int i = k; i >= 1; --i)
        fout << fixed << setprecision(12) << b[i].x << " " << b[i].y << "\n";
}
int main(){
    read();
    convex_hull();
    write();
    return 0;
}
/*
task:

*/