Cod sursa(job #1756626)

Utilizator dtoniucDaniel Toniuc dtoniuc Data 13 septembrie 2016 10:57:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

typedef struct point
{
	double x, y;
public:
	point(double x, double y) : x(x), y(y) {};
}Point;

bool cmp(Point* p1, Point* p2)
{
	if(p1->x == p2->x)
		return p1->y < p2->y;
	else
		return p1->x < p2->x;
}

double CrossProduct(Point* O, Point* A, Point* B)
{
	return (A->x - O->x) * (B->y - O->y) - (A->y  - O->y) * (B->x - O->x);
}

int main()
{
    ifstream fin;
    ofstream fout;
    fout.open("infasuratoare.out");
    fin.open("infasuratoare.in");

    int n;
	double x, y;
    const double EPS = 1e-12;
    fin >> n;
    Point** pointsList = new Point*[n + 1]();
    for(int i = 1; i <= n; i++)
    {
    	fin >> x >> y;
    	pointsList[i] = new Point(x,y);
    }

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

    bool *viz = new bool[n + 1]();
    int st[n + 1];
    int head = 2;
    st[1] = 1; st[2] = 2;
    viz[2] = true;

    for(int i = 1, p = 1; i > 0; i += ( p = (i == n ? -p : p)))
    {
    	if(viz[i]) continue;

    	while(head >= 2 && CrossProduct(pointsList[st[head - 1]], pointsList[st[head]], pointsList[i]) < EPS)
    	{
    		viz[st[head--]] = false;
    	}

    	st[++head] = i;
    	viz[i] = true;
    }

    fout << head - 1 << "\n";
    fout << setprecision(6) << fixed;
    for(int i = 1; i < head; i++)
    	fout << pointsList[st[i]]->x << " " << pointsList[st[i]]->y << "\n";
    fin.close();
    fout.close();
    return 0;
}