Cod sursa(job #2539735)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 6 februarie 2020 11:06:06
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iomanip>

using namespace std;

double Lx, Ly;

struct point {
	double x, y;
	void init(double a, double b)
	{
		x = a;
		y = b;
	}
	bool operator==(const point& other)
	{
		return ((x == other.x) && (y == other.y));
	}
	double getPanta() 
	{
		double val = y / x;
		return val;
	}
	void print()
	{
		cout << x << " " << y << "\n";
	}
};

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

int semn(point a, point b, point c)
{
	double val = (a.x - b.x) * (a.y - c.y) - (a.y - b.y) * (a.x - c.x);
	if (val >= 0)
		return 1;
	else if (val < 0)
		return -1;
}

point st[125005];
int top = 0;
vector<point>p;
vector<point>v;

int main()
{
	ifstream cin("infasuratoare.in");
	ofstream cout("infasuratoare.out");
	int n;
	cin >> n;
	double a, b;
	point LL;
	LL.init(1e9, 1e9);
	for (int i = 1; i <= n; i++)
	{
		cin >> a >> b;
		point temp;
		temp.init(a, b);
		if (LL.y > b) {
			LL.y = b;
			LL.x = a;
		}
		else if (LL.y == b)
		{
			if (LL.x > a)
				LL.x = a;
		}
		p.push_back(temp);
	}
	for (int i = 1; i < p.size(); i++)
	{
		if (LL == p[i])
			swap(p[0], p[i]);
		p[i].x -= LL.x;
		p[i].y -= LL.y;
	}
	p[0] = { 0,0 };
	sort(p.begin() + 1,p.end(),cmp);
	st[++top] = p[0];
	st[++top] = p[1];
	st[++top] = p[2];
	for (int i = 3; i < p.size(); i++)
	{
		while (top >= 2 && semn(st[top - 2], st[top - 1], st[top]) != semn(st[top - 1], st[top], p[i]))
			top--;
		st[++top] = p[i];
	}
	cout << top << "\n";
	for (int i = 1; i <= top; i++)
		cout << fixed << setprecision(6) << st[i].x + LL.x << " " << st[i].y+LL.y << "\n";
	return 0;
}