Cod sursa(job #2539726)

Utilizator Iulia25Hosu Iulia Iulia25 Data 6 februarie 2020 10:53:24
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

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

int n, top;
long double x = 2e9, y = 2e9;

struct idk	{
	long double x, y;
} stiva[120005], a[120005];

bool semn(idk x1, idk x2, idk x3)	 {
  long double ans = (x1.x - x2.x) * (x1.y - x3.y) - (x1.y - x2.y) * (x1.x - x3.x);
  return (ans > 0);
}

bool cmp(idk _x, idk _y)	{
	return semn({0, 0}, _x, _y);
}

int main()	{
  fin >> n;
  for (int i = 1; i <= n; ++i)	{
    fin >> a[i].x >> a[i].y;
    if (a[i].y <= y)	 {
			if (a[i].y == y && a[i].x < x)
				x = a[i].x;
			else if (a[i].y < y)	{
				y = a[i].y;
				x = a[i].x;
			}
		}
  }
	for (int i = 1; i <= n; ++i)	{
		a[i].x -= x;
		a[i].y -= y;
		if (a[i].x == 0 && a[i].y == 0)
			swap(a[1], a[i]);
	}
	sort (a + 2, a + n + 1, cmp);
	stiva[++top] = a[1];
	stiva[++top] = a[2];
	for (int i = 3; i <= n; ++i)	{
    while (top >= 2 && !semn(stiva[top - 1], stiva[top], a[i]))
			--top;
		stiva[++top] = a[i];
	}
	fout << top << '\n';
	fout << fixed << setprecision(12);
	for (int i = 1; i <= top; ++i)
		fout << stiva[i].x + x << ' ' << stiva[i].y + y << '\n';
	return 0;
}