Cod sursa(job #2074060)

Utilizator GabiMrgineanGabi M. GabiMrginean Data 24 noiembrie 2017 01:25:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb

///GRAHAM SCAN

#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <stdlib.h>

using namespace std;

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

typedef pair<double,double> Point;
#define x first
#define y second

int n,head;
Point *points;
Point *Stack;

void ReadAndAlloc()
{
	in>>n;
	points = (Point*)malloc(sizeof(Point) * (n+5)), Stack = (Point*)malloc(sizeof(Point) * (n+5));
	for (int i=1;i<=n;i++)
		in>>points[i].x>>points[i].y;
    in.close();
}

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

bool cmp(Point p1, Point p2)
{
    return CrossProduct(points[1], p1, p2) < 0;
}

void SortPoints() {
    int pos = 1;
    for (int i = 2; i <= n; ++i)
        if (points[i] <= points[pos])
            pos = i;
    swap(points[1], points[pos]);
    sort(points + 2, points + n + 1, cmp);
}

void Print(Point a[])
{
	for (int i=1; i<=n;i++)
		out<<fixed<<a[i].x<<" "<<a[i].y<<'\n';
}

void DoHull()
{
    Stack[1] = points[1];
    Stack[2] = points[2];
    head = 2;
    for (int i=3;i<=n;++i){
        while (head >= 2 && CrossProduct(Stack[head - 1], Stack[head], points[i]) > 0)
            --head;
    Stack[++head] = points[i];
    }
}

void PrintHull()
{
    out<<fixed;
    out<<head<<'\n';
    for (int i=head;i>=1;--i)
        out<<setprecision(9)<<Stack[i].x<<" "<<Stack[i].y<<'\n';
    out.close();
}

int main()
{
	ReadAndAlloc();
	SortPoints();
	DoHull();
	PrintHull();
	return (0);
}