Cod sursa(job #3296036)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 10 mai 2025 21:02:14
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
// #include <bits/stdc++.h>
#define in  fin
#define out fout

using namespace std;
using db = long double;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct punct{
    db x, y;

    bool operator==(const punct & A) const {
        return (A.x == x && A.y == y);
    }
};

db det(punct A, punct B, punct C){
    return A.x * B.y + B.x * C.y + C.x * A.y - 
        A.x * C.y - B.x * A.y - C.x * B.y;
}

punct start;
bool cmp(punct A, punct B){
    if(det(start, A, B) < 0) return true;
    else return false;
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    int n; in >> n;
    punct v[n];
    start.x = start.y = INT_MAX;

    for(int i = 0; i < n; i++){
        in >> v[i].x >> v[i].y;
        if( start.x > v[i].x ) start = v[i];
        else if(start.x == v[i].x && start.y > v[i].y) start = v[i];
    }

    int p = 0;
    for(int i = 0; i < n; i++){
        if(start == v[i]) p = i;
    }

    swap(v[0], v[p]);

    sort(v + 1, v + n, cmp);

    // cout << "Dupa sort : \n";
    // for(int i = 0; i < n; i++) cout << v[i].x << " " << v[i].y << '\n';
    // cout << '\n';

    vector<punct> s;
    s.push_back(v[0]);
    for(int i = 1; i < n; i++){
        while(s.size() >= 2){
            punct A = s.back();
            punct B = s[s.size() - 2];

            if(det(B, A, v[i]) > 0) s.pop_back();
            else break;
        }
        s.push_back(v[i]);
    }
    out << s.size() << "\n";
    for(int i = 0; i < s.size(); i++) out << s[i].x << " " << s[i].y << '\n';

    return 0;
}