Cod sursa(job #2532534)

Utilizator XsoundCristian-Ioan Roman Xsound Data 27 ianuarie 2020 22:24:10
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.53 kb
#include <bits/stdc++.h>
#define Dmax 1000000005
using namespace std;
ifstream fin ( "infasuratoare.in" );
ofstream fout ( "infasuratoare.out" );
struct Point
{
    double x, y;

    friend bool operator < ( Point a, Point b );
};

vector < Point > s;
vector < Point > v;
Point refPoint;
int n, lng, imin;

void read ( );
void Infasuratoare ( );
bool Arie ( Point a );

int main ( )
{
    read ( );

    sort ( v.begin(), v.end() );

    /*for ( int i = 0; i < n; i++ )
        fout << v[i].x << ' '<< v[i].y << '\n';

    fout << "\n\n\n\n";*/

    Infasuratoare ( );

    fout << lng+1 << '\n';

    setprecision(15);

    for ( int i = imin; i <= lng; i++ )
        fout << fixed << s[i].x << ' ' << s[i].y << '\n';

    for ( int i = 0; i < imin; i++ )
        fout << fixed << s[i].x << ' ' << s[i].y << '\n';
}

bool Arie ( Point c )
{
    Point a, b;

    vector < Point > :: iterator it;

    it = s.end();

    --it;

    b = *it;
    a = *(--it);

    double det =( a.x*b.y + a.y*c.x + c.y*b.x ) - ( b.y*c.x + c.y*a.x + a.y*b.x );

    if ( det > 0 )
        return 1;
    else if ( det < 0 )
        return 0;

    else
    {
        bool sens = 0;

        if ( b.x > a.x || b.y > a.y )
            sens = 1;

        if ( sens == 0 )
        {
            if ( c.x < b.x || c.y < b.y )
                return 1;
            return 0;
        }

        else
        {
            if ( c.x > b.x || c.y > b.y )
                return 1;
            return 0;
        }
    }
}

void Infasuratoare ( )
{
    s.push_back ( v[0] );
    s.push_back ( v[1] );

    stack < int > sol;

    lng = 1;

    if ( v[0].y < v[1].y )
        sol.push(0);
    else if ( v[0].y > v[1].y )
        sol.push(1);
    else if ( v[0].x < v[1].x )
        sol.push(0);
    else
        sol.push(1);

    for ( int i = 2; i < n; i++ )
    {
        if ( Arie ( v[i] ) == 0 )
        {
            s.erase ( --s.end() );
            i--;
            if ( lng == sol.top() )
                sol.pop( );
            lng--;
        }
        else
        {
            lng++;
            s.push_back ( v[i] );

            if ( s[lng].y < s[sol.top()].y )
                sol.push(lng);

            else if ( s[lng].y == s[sol.top()].y && s[lng].x < v[sol.top()].x )
                sol.push(lng);

        }
    }

    imin = sol.top();
}

void read ( )
{
    refPoint.x = Dmax;
    refPoint.y = Dmax;

    Point p;

    fin >> n;

    for ( int i = 1; i <= n; i++ )
    {
        fin >> p.x >> p.y;
        v.push_back ( p );

        if ( p.x < refPoint.x )
            refPoint = p;
        else if ( p.x == refPoint.x && p.y < refPoint.y )
            refPoint = p;
    }
}

bool operator < ( Point a, Point b )
{
    if ( a.x == refPoint.x && a.y == refPoint.y )
        return 1;
    if ( b.x == refPoint.x && b.y == refPoint.y )
        return 0;

    double r1, r2, ip1, ip2;

    r1 = abs ( a.y - refPoint.y ) * 1.0;

    ip1 = sqrt( (a.x-refPoint.x)*(a.x-refPoint.x) + (a.y-refPoint.y)*(a.y-refPoint.y) );

    r1/=ip1;

    r2 = abs ( b.y - refPoint.y ) * 1.0;

    ip2 = sqrt( (b.x-refPoint.x)*(b.x-refPoint.x) + (b.y-refPoint.y)*(b.y-refPoint.y) );

    r2/=ip2;

    if ( a.y > refPoint.y )
        r1*=-1;
    if ( b.y > refPoint.y )
        r2*=-1;

    if ( r1 > r2 )
        return 1;

    if ( r1 < r2 )
        return 0;

    if ( a.y <= refPoint.y )
        return ip1 < ip2;
    else
        return ip1 > ip2;
}