Cod sursa(job #2890882)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 16 aprilie 2022 21:19:39
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.46 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

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

int N, M;

struct point{
    long double x, y;

    const bool operator == ( const point& pt ){
        return x == pt.x && y == pt.y;
    }
    friend istream &operator >> ( istream  &in, point& pt ) {
         in >> pt.x >> pt.y;
         return in;
    }
    friend ofstream &operator << ( ofstream &out, point& pt ){
        out << fixed << setprecision(6) << pt.x << ' ' << pt.y << '\n';
        return out;
    }
}P[120002], A, B;

long long orientation( point P, point Q, point R ){
    return (Q.y-P.y) * (R.x-Q.x) - (Q.x-P.x) * (R.y-Q.y);
}

int Query( int lf, int rg, point Q){

    if( rg - lf + 1 <= 3 ){
        if( orientation(P[lf], P[lf+1], Q ) < 0 && orientation( P[rg], P[rg-1], Q ) > 0 )
            return 1;
        if( orientation(P[lf], P[lf+1], Q ) > 0 || orientation( P[rg], P[rg-1], Q ) < 0 )
            return -1;
        return 0;
    }
    int mid = (lf + rg)/2;
    long long val = orientation( P[lf], P[mid], Q );

    if( val == 0 ){
        if( Q == P[lf] || Q == P[mid] ) return 0;
        if( P[lf].x <= Q.x && Q.x <= P[mid].x && P[lf].y <= Q.y && Q.y <= P[mid].y ) return 1;
        return -1;
    }
    if( val < 0 )
        return Query( mid, rg, Q );
    if( val > 0 )
        return Query( lf, mid, Q );
}

bool comp( const point& A, const point& B ){
    return orientation( P[1], A, B ) < 0;
}
vector < point > Hull;

int main()
{
    fin >> N;

    int first = 1;
    for( int i = 1; i <= N; ++i ){
        fin >> P[i];
        if( P[i].x < P[first].x || P[i].x == P[first].x && P[i].x < P[first].x )
            first = i;
    }
    swap( P[1], P[first] );
    sort( P+2, P+N+1, comp );

    Hull.push_back( P[1] );
    Hull.push_back( P[2] );

    for( int i = 3; i <= N; ++i ){
        A = Hull[Hull.size() - 2];
        B = Hull[Hull.size() - 1];

        if( orientation( A, B, P[i] ) < 0 )
            Hull.push_back( P[i] );

        else {
            while( orientation( A, B, P[i] ) >= 0 ){
                Hull.pop_back();
                B = A;
                A = Hull[Hull.size() - 2];
            }
            Hull.push_back( P[i] );
        }
    }

    fout << Hull.size() << '\n';
    for( int i = 0; i < Hull.size(); ++i )
        fout << Hull[i];
    return 0;
}