Cod sursa(job #3270031)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 21 ianuarie 2025 19:55:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <iomanip>
#include <algorithm>
//#include <bits/stdc++.h>
#define in fin
#define out fout

using namespace std;
using db = double;

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

struct punct{
    db x, y;
    bool operator == (punct b){
        return (x == b.x && y == b.y);
    }
};

punct p0; // reference

db det(punct a, punct b, punct c){
    a.x -= c.x;
    b.x -= c.x;
    a.y -= c.y;
    b.y -= c.y;
    return a.x * b.y - a.y * b.x;
}

bool cmp( punct a, punct b ){
    if(a == p0) return true;
    if(b == p0) return false;

    return (det(p0, a, b) > 0);
}

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

    int n; in >> n;
    punct v[n];
    db offsetx = 0, offsety = 0;

    p0.x = p0.y = 1000000000;
    for(int i = 0; i < n; i++){
        in >> v[i].x >> v[i].y;

        if(v[i].x < p0.x){ p0.x = v[i].x; p0.y = v[i].y; }
        else if(v[i].x == p0.x) p0.y = min(p0.y, v[i].y);

    }
    // cout << "p0 = " << p0.x << " " << p0.y << '\n';  

    sort(v + 0, v + n, cmp);
    vector< punct > s;
    for(int i = 0; i < n; i++){
        // cout << "i = " << i << " ( " << v[i].x << " , " << v[i].y << " )\n"; 
        while(s.size() >= 2){
            punct y = s[s.size() - 1];
            punct x = s[s.size() - 2];

            // cout << "  -- > comparam cu x = ( " << x.x << " , " << x.y << " )\n";
            // cout << "  -- > comparam cu y = ( " << y.x << " , " << y.y << " )\n";

            if(det(x, y, 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 << fixed << setprecision(12) << s[i].x << " " << s[i].y << '\n';
    }

    return 0;
}