Cod sursa(job #2683095)

Utilizator andrei.florea0405Florea Andrei-Bogdan andrei.florea0405 Data 10 decembrie 2020 14:50:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;

typedef pair<double, double> Point;
	
 
	
ifstream fin("infasuratoare.in");
	
ofstream fout("infasuratoare.out");
	
 
	
const int MAX_N = 120005;

int n, k;	
Point v[MAX_N];
Point stiva[MAX_N];
 
	
inline double cross_product(const Point& A, const Point& B, const Point& C) {
    return (B.first - A.first) * (C.second - A.second) 
    - (B.second - A.second) * (C.first - A.first);
}

	
inline int cmp(const Point& p1, const Point& p2) {
    return cross_product(v[1], p1, p2) < 0;	
}
	
 
void sort_points() {
    int pos = 1;
    for (int i = 2; i <= n; ++i)
        if (v[i] < v[pos])
            pos = i;
	
    swap(v[1], v[pos]);
    sort(v + 2, v + n + 1, cmp);
}

	
void convex_hull() {
    sort_points();
	
    stiva[1] = v[1];
    stiva[2] = v[2];
    k = 2;
	
    for (int i = 3; i <= n; ++i) {
        while (k >= 2 && cross_product(stiva[k - 1], stiva[k], v[i]) > 0)
            --k;
	
        stiva[++k] = v[i];
    }

    fout << fixed << setprecision(9);
    fout << k << "\n";
    for (int i = k; i >= 1; --i)
        fout << stiva[i].first << " " << stiva[i].second << "\n";
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i].first >> v[i].second;
	
    convex_hull();
	
    
    return 0;
}