Cod sursa(job #2030362)

Utilizator borcanirobertBorcani Robert borcanirobert Data 1 octombrie 2017 15:20:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

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

const int MAX = 120010;
struct Point{
    double x, y;
};
Point A;

void ReadPoints( Point a[MAX], int& N );
void GrahamScan( Point a[MAX], Point st[MAX], int N, int& top );
void Sort( Point a[MAX], int N );
double CrossProduct( Point a, Point b, Point c );
void Write( Point st[MAX], int N );
bool CompPoints( const Point& p1, const Point& p2 );

int main()
{
    Point a[MAX], res[MAX];
    int N, M;

    ReadPoints(a, N);
    GrahamScan(a, res, N, M);
    Write(res, M);

    fin.close();
    fout.close();
    return 0;
}

void ReadPoints( Point a[MAX], int& N )
{
    fin >> N;
    for ( int i = 1; i <= N; ++i )
        fin >> a[i].x >> a[i].y;
}

void GrahamScan( Point a[MAX], Point st[MAX], int N, int& top )
{
    Sort(a, N);

    top = 2;
    st[1] = a[1];
    st[2] = a[2];

    for ( int i = 3; i <= N; ++i )
    {
        while (top >= 2 && CrossProduct(st[top - 1], st[top], a[i]) < 0)
            --top;
        st[++top] = a[i];
    }
}

void Sort( Point a[MAX], int N )
{
    for ( int i = 2; i <= N; ++i )
        if ( a[i].y < a[1].y || ( a[i].y == a[1].y && a[i].x < a[1].x ) )
            swap(a[i], a[1]);
    A = a[1];

    sort(a + 2, a + N + 1, CompPoints);
}

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

void Write( Point st[MAX], int N )
{
    fout << N << '\n';
    for ( int i = 1; i <= N; ++i )
        fout << fixed << setprecision(12) << st[i].x << ' ' << st[i].y << '\n';
}

bool CompPoints( const Point& p1, const Point& p2 )
{
    return CrossProduct(A, p1, p2) > 0;
}