Cod sursa(job #2774761)

Utilizator AsakariGeicu Emil Asakari Data 12 septembrie 2021 18:00:44
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.32 kb
#include <iostream>
#include <fstream> 
#include <stack>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct
{
	double x, y;
};
Punct punctinit;
Punct nextToTop(stack<Punct>& S)
{
	Punct p = S.top();
	S.pop();
	Punct res = S.top();
	S.push(p);
	return res;
}
int orientare(Punct pst, Punct pint, Punct pfin)
{
	int ok = (pint.y - pst.y) * (pfin.x - pint.x) - (pint.x - pst.x) * (pfin.y - pint.y);
	if (ok == 0)
		return 0;
	if (ok > 0)
		return 1;
	else
		return 2;
}

double distanta(Punct p1, Punct p2)
{
	return (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.x) * (p2.y - p1.x);
}

int criteriu(const void* nr1, const void* nr2)
{
	Punct* p1 = (Punct*)nr1;
	Punct* p2 = (Punct*)nr2;
	int ok = orientare(punctinit, *p1, *p2);
	if (ok == 0)
	{
		if (distanta(punctinit, *p2) >= distanta(punctinit, *p1))
			return -1;
		else
			return 1;
	}
	if (ok== 2)
		return -1;
	else
		return 1;
}
void puncte_poligon(vector<Punct> puncte, int n)
{
	double ymin, minpos=0;
	ymin = puncte[0].y;
	for(int i=1;i<n;i++)
		if ((puncte[i].y < ymin) || (puncte[i].y == ymin && puncte[i].x < puncte[minpos].x))
		{
			ymin = puncte[i].y;
			minpos = i;
		}
	Punct aux;
	aux = puncte[0];
	puncte[0] = puncte[minpos];
	puncte[minpos] = aux;
	punctinit = puncte[0];
	qsort(&puncte[1], n - 1, sizeof(Punct), criteriu);
	
	int nr = 1;
	for (int i = 1; i < n; i++)
	{
		while (i < n - 1 && orientare(punctinit, puncte[i], puncte[i + 1]) == 0)
			i++;
		puncte[nr] = puncte[i];
		nr++;
	}
	if (nr < 3)
		return;
	stack<Punct> Spuncte;
	Spuncte.push(puncte[0]);
	Spuncte.push(puncte[1]);
	Spuncte.push(puncte[2]);
	
	for (int i = 3; i < nr; i++)
	{
		while (Spuncte.size() > 1 && orientare(nextToTop(Spuncte), Spuncte.top(), puncte[i]) != 2)
			Spuncte.pop();
		Spuncte.push(puncte[i]);
	}
	g << Spuncte.size() << "\n";
	while (!Spuncte.empty())
	{
		Punct p = Spuncte.top();
		g<<setprecision(6)<<fixed<< "(" << p.x << ", " << p.y << ")" <<"\n";
		Spuncte.pop();
	}
}
int main()
{	
	int n;
	vector<Punct> puncte;
	f >> n;
	for (int i = 0; i < n; i++)
	{
		Punct punct;
		f >> punct.x >> punct.y;
		puncte.push_back(punct);
	}
	puncte_poligon(puncte, n);
	return 0;
}