Cod sursa(job #3210257)

Utilizator AndreiMLCChesauan Andrei AndreiMLC Data 5 martie 2024 17:51:44
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <iomanip>
#include <algorithm>

using namespace std;

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

struct punct
{
	long double x;
	long double y;
	long double angle;
};

const int nmax = 125005;
int n;
punct puncte[nmax];
int hull[nmax];
int h; //inaltimea hull-ului -> ca sa stiu pe unde ma aflu


void citire()
{
	f >> n;
	for (int i = 0; i < n; i++)
	{
		f >> puncte[i].x >> puncte[i].y;
	}
}

bool counter_clock(punct a, punct b, punct c)
{
	return ((b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y)) < 0;
}

void graham()
{
	hull[0] = 0;
	hull[1] = 1;
	h = 2;
	for (int i = 2; i < n; i++)
	{
		while (h >= 2 && !counter_clock(puncte[hull[h - 2]], puncte[hull[h - 1]], puncte[i]))
		{
			h--;
		}
		hull[h] = i;
		h++;
	}
}

void solve()
{
	for (int i = 1; i < n; i++)
	{
		if (puncte[i].y < puncte[0].y)
		{
			swap(puncte[0].y , puncte[i].y);
		}
	}

	puncte[0].angle = 0;

	for (int i = 1; i < n; i++)
	{
		puncte[i].angle = atan2(puncte[i].y - puncte[0].y, puncte[i].x - puncte[0].x);
	}

	sort(puncte + 1, puncte + n, [](punct a, punct b) {
			return a.angle < b.angle;
		});

	/*
	for (int i = 0; i < n; i++)
	{
		g << puncte[i].x << ' ' << puncte[i].y << ' ' << puncte[i].angle << '\n';
	}*/

	graham();

	g << h << '\n';
	for (int i = 0; i < h; i++)
	{
		int indx = hull[i];
		g << fixed << setprecision(6) << puncte[indx].x << " ";
		g << fixed << setprecision(6) << puncte[indx].y;
		g << '\n';
	}
}

int main()
{
	citire();
	solve();
}