Cod sursa(job #3270005)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 21 ianuarie 2025 18:53:02
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.42 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;
};

punct p0; // reference

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

    return (( a.x * b.y - b.x * a.y ) > 0);
}

db det(punct a, punct b, punct c){
    db x1 = a.x, x2 = b.x, x3 = c.x;
    db y1 = a.y, y2 = b.y, y3 = c.y;

    return x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3;
}

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

    int n; in >> n;
    punct v[n];

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

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

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

    // for(int i = 0; i < n; i++){
    //     cout << "( " << v[i].x << " , " << v[i].y << " )\n";
    // } // sortate

    stack< punct > s;
    s.push( v[0] );
    s.push( v[1] );

    for(int i = 2; i < n; i++){
        // cout << "i = " << i << " ( " << v[i].x << " , " << v[i].y << " )\n"; 
        while(s.size() >= 2){
            punct x = s.top(); s.pop();
            punct y = s.top(); s.pop();

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

            if(det(y, x, v[i]) > 0){
                // cout << "  -- > GUD\n";
                s.push(y);
                s.push(x);
                break;
            }

            s.push(y);
            // cout << "  -- > Scoatem x\n";
        }
        s.push(v[i]);
    }

    vector< punct > sol;
    sol.push_back( s.top() ); s.pop();
    while(!s.empty()){
        sol.push_back( s.top() );
        s.pop();
    }
    
    p0.x = p0.y = INT_MIN;

    sort(sol.begin(), sol.end(), cmp);

    out << sol.size() << '\n';
    for(int i = 0; i < sol.size(); i++){
        out << fixed << setprecision(12) << sol[i].x << " " << sol[i].y << '\n';
    }
    // out << fixed << setprecision(12) << sol[0].x << " " << sol[0].y << '\n';

    return 0;
}