Cod sursa(job #1579573)

Utilizator deresurobertoFMI - Deresu Roberto deresuroberto Data 24 ianuarie 2016 21:15:22
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
//Roberto Deresu - FMI
//Re :)
#include <iostream>
#include <fstream>
#include <climits>
#define nx 120007
using namespace std;

int n, m;

struct Point
{
    double x;
    double y;
} *points, *march, first, current, nextp;

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

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);
}

int main()
{
    fin >> n;

    first.x = first.y = INT_MAX;
    points = new Point[n];
    march = new Point[n];

    for (int index = 0; index < n; index++)
    {
        fin >> points[index].x >> points[index].y;

        if (points[index].x < first.x || (points[index].x == first.x && points[index].y < first.y))
        {
            first = points[index];
        }
    }

    current = first;

    while (first.x != nextp.x || first.y != nextp.y) //first != nextp
    {
        if (points[0].x == current.x && points[0].y == current.y)
        {
            nextp = points[1];
        }
        else
        {
            nextp = points[0];
        }

        for (int index = 0; index < n; index++)
        {
            if (CrossProduct(current, nextp, points[index]) < 0)
            {
                nextp = points[index];
            }
        }

        march[m++] = nextp;
        current = nextp;
    }

    fout << m << "\n";

    fout.setf( std::ios::fixed, std:: ios::floatfield);
    fout.precision(6);

    for (int index = 0; index < m; index++)
    {
        fout << march[index].x << " " << march[index].y << "\n";
    }

    return 0;
}