Cod sursa(job #1829249)

Utilizator Firealex2Rotileanu Alexandru Firealex2 Data 14 decembrie 2016 17:59:53
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.36 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct point {
	double x, y;
};

const int maxn = 120000;

bool cmp(point a, point b);
double sarrus(double x1, double y1, double x2, double y2, double x3, double y3);
void convex_hull();
void init();
void show();

point SINF[maxn + 1], SSUP[maxn + 1], POINTS[maxn + 1], aux, pmin, pmax;
int N, inf_count, sup_count;

int main()
{
	fi >> N;
	init();
	convex_hull();
	show();
	return 0;
}

void init()
{
	pmin.x = 9999999999.0;
	for (int i = 1;i <= N;i++)
	{
		fi >> POINTS[i].x >> POINTS[i].y;
		if (POINTS[i].x < pmin.x)
			pmin = POINTS[i];
		if (POINTS[i].x > pmax.x)
			pmax = POINTS[i];
	}

	SINF[++inf_count] = pmin;
	SINF[++inf_count] = pmax;
	SSUP[++sup_count] = pmin;
	SSUP[++sup_count] = pmax;

	for (int i = 1;i <= N;i++)
	{
		if (sarrus(pmax.x, pmax.y, pmin.x, pmin.y, POINTS[i].x, POINTS[i].y) < 0)
			SSUP[++sup_count] = POINTS[i];
		else if(sarrus(pmax.x, pmax.y, pmin.x, pmin.y, POINTS[i].x, POINTS[i].y) > 0) SINF[++inf_count] = POINTS[i];
	}

	sort(SSUP + 1, SSUP + sup_count + 1, cmp);
	sort(SINF + 1, SINF + inf_count + 1, cmp);
}

bool cmp(point a, point b)
{
	if (a.x == b.x)
		return (a.y < b.y);
	return (a.x < b.x);
}

double sarrus(double x1, double y1, double x2, double y2, double x3, double y3)
{
	double s = 0.0;
	s = x2*y1 + x1*y3 + y2*x2 - y1*x2 - y3*x2 - y2*x1;
	return s;
}

void convex_hull()
{
	int i = 1;
	while (i + 2 <= inf_count)
	{
		point p1 = SINF[i], p2 = SINF[i + 1], p3 = SINF[i + 2];
		if (sarrus(p3.x, p3.y, p1.x, p1.y, p2.x, p2.y) > 0) i++;
		else {
			for (int j = i + 1;j <= inf_count; j++)
				SINF[j] = SINF[j + 1];
			inf_count--;
		}
	}

	i = 1;

	while (i + 2 <= sup_count)
	{
		point p1 = SSUP[i], p2 = SSUP[i + 1], p3 = SSUP[i + 2];
		if (sarrus(p3.x, p3.y, p1.x, p1.y, p2.x, p2.y) < 0) i++;
		else {
			for (int j = i + 1;j <= sup_count; j++)
				SSUP[j] = SSUP[j + 1];
			sup_count--;
		}
	}

	return;
}


void show()
{
	fo << inf_count + sup_count - 1 << '\n';
	fo << setprecision(6) << fixed;
	for (int i = 2;i <= sup_count;i++)
		fo << SSUP[i].x << " " << SSUP[i].y << '\n';
	for (int i = inf_count;i >= 1;i--)
		fo << SINF[i].x << " " << SINF[i].y << '\n';
	return;
}