Cod sursa(job #3241949)

Utilizator Dani111Gheorghe Daniel Dani111 Data 6 septembrie 2024 16:37:21
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;

const int MAX = 2 * 1e5;

struct point{
    double x, y;
}A[MAX + 3];

int N;  
vector<int>s;
vector<int>s1;
bool v[MAX + 3];
double F(point O, point A, point B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x); 
}

set<int>s3;

bool cmp(point a, point b) {
    if(a.x < b.x) return true;
    if(a.x == b.x) return a.y < b.y;
}

int main() {
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> A[i].x >> A[i].y;
    }
    
    sort(A + 1, A + N + 1, cmp);

    s.push_back(2); 
    s.push_back(1); 

    for(int i = 1; i <= N; i++) {
        while(s.size() >= 2 && F(A[s[s.size() - 2]], A[s[s.size() - 1]], A[i]) < 0) {
            s.pop_back();
        }
        s.push_back(i);
    }

    for(auto i : s) {
        s3.insert(i);
    }

    for(int i = N; i >= 1; i--) {
        while(s1.size() >= 2 && F(A[s1[s1.size() - 2]], A[s1[s1.size() - 1]], A[i]) < 0) {
            s1.pop_back();
        }

        s1.push_back(i);
    }   

    
    for(auto i : s1) {
        s3.insert(i);
    }
    cout << setprecision(8);
    cout << s3.size() << '\n';
    for(auto i : s3) {
        cout << A[i].x << ' ' << A[i].y << '\n';
    }
}