Cod sursa(job #2953517)

Utilizator teodorescunicolasteodorescu nicolas alexandru teodorescunicolas Data 11 decembrie 2022 16:54:51
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

#define NMAXX 120000

using namespace std;

struct Point {
    double x, y;
};

vector <Point> convex;
Point v[NMAXX];

int findStartPoint( int n ) {
    int start = 0, i;

    for ( i = 1; i < n; i++ )
        if ( v[i].y < v[start].y || ( v[i].y == v[start].y && v[i].x < v[start].x ) )
            start = i;

    return start;
}

double orientare( const Point &a, const Point &b, const Point &c ) {
    return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
}

bool cmp( const Point &a, const Point &b ) {
    return orientare( v[0], a, b ) < 0;
}

void compute( int n ) {
    int i;

    convex.push_back( v[0] );
    convex.push_back( v[1] );

    for ( i = 2; i < n; i++ ) {
        while ( convex.size() >= 2 && orientare( convex[convex.size() - 2], convex.back(), v[i] ) >= 0 )
            convex.pop_back();

        convex.push_back( v[i] );
    }
}

int main()
{
    FILE *fin, *fout;
    int n, i;

    fin = fopen( "infasuratoare.in", "r" );
    fout = fopen( "infasuratoare.out", "w" );

    fscanf ( fin, "%d", &n );
    for ( i = 0; i < n; i++ )
        fscanf( fin, "%lf%lf", &v[i].x, &v[i].y );

    swap( v[0], v[findStartPoint( n )] );

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

    compute( n );

    fprintf( fout, "%d\n", convex.size() );
    for ( const Point &p : convex )
        fprintf( fout, "%lf %lf\n", p.x, p.y );

    fclose( fin );
    fclose( fout );
    return 0;
}