Cod sursa(job #2936401)

Utilizator Nico10Nicola Andrei George Nico10 Data 8 noiembrie 2022 19:32:06
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.55 kb
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
using namespace std;

struct Punct{
    long double x, y; }p, Start;
void Graham_scan(vector<Punct>&v, vector<Punct>&sol);
int orientare(Punct a, Punct b, Punct c);
bool comparator(Punct a, Punct b);
void input(vector<Punct>&v);
void output(vector<Punct>sol);

vector<Punct> v, sol;
fstream f, g;
int n;

int main()
{
    input(v);
    Graham_scan(v, sol);
    output(sol);
    return 0;
}
void Graham_scan(vector<Punct>&v, vector<Punct>&sol){
    Punct Start = v[0];
    int i, dim = v.size()-1;
    for( i = 1; i < v.size(); ++i)
        if( v[i].y < Start.y or v[i].y == Start.y and v[i].x < Start.x)
            Start = v[i];
    ///pana aici am gasit punctul din stanga jos minim
    sort(v.begin(), v.end(), comparator);

    while( dim >= 0 and orientare(Start, v[dim], v.back()) == 1 )
        --dim;
    reverse( v.begin()+dim+1, v.end() );

    Punct A, B, C;
    for( i = 0; i < v.size(); ++i )
    {
        while( sol.size() > 1 )
        {

            A = sol[ sol.size() - 2];
            B = sol.back();
            C = v[i];
            int arie = orientare(A, B, C);
            if(arie > 0) sol.pop_back();
            else break;
        }
        sol.push_back( v[i] );
    }
}
void input(vector<Punct>&v){
    ios::sync_with_stdio(false);
    f.open(IN, ios::in);
    g.open(OUT, ios::out);
    f >> n;
    g << fixed << setprecision(6);
    for(int i = 0; i < n; i++){
        f >> p.x >> p.y;
        v.push_back(p);
    }
    f.close();
}
void output(vector<Punct>sol){
    g << sol.size() << '\n';
    for(int i = sol.size()-1; i >= 0; --i)
        g << sol[i].x <<' '<<sol[i].y<<'\n';
    g.close();
}
int orientare(Punct A, Punct B, Punct C){
    long double panta = A.x * (B.y - C.y)  +  B.x * (C.y - A.y)  +  C.x * (A.y - B.y);
    if( panta > 0 ) return 1;
    else if( !panta ) return 0;
    return -1;
}
bool comparator(Punct A, Punct B){
    int arie = orientare(Start, A, B);
    if( !arie )
    {
        long double d_Start_A_patrat = (A.x - Start.x)*(A.x - Start.x) + (A.y - Start.y)*(A.y - Start.y);///folsoesc dezvoltarea Gauss-Jacobi
        long double d_Start_B_patrat = (B.x - Start.x)*(B.x - Start.x) + (B.y - Start.y)*(B.y - Start.y);///de asemenea pot folosi si raportul pantelor
        if( A.y == B.y ) return(d_Start_A_patrat > d_Start_B_patrat);
        return (d_Start_A_patrat  <  d_Start_B_patrat);
    }
    return arie < 0;
}