Cod sursa(job #2539673)

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

using namespace std;

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

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

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

bool cmp(idk _x, idk _y)	{
	double x1 = _x.y / _x.x;
	double x2 = _y.y / _y.x;
	if (x1 < 0 && x2 < 0)
    return (x1 < x2);
	if (x1 > 0 && x2 > 0)
		return (x1 < x2);
  if (x1 >= 0 && x2 < 0)
		return true;
	return false;
}

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

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;
	}
	sort (a + 1, a + n + 1, cmp);
	stiva[++top] = a[1];
	stiva[++top] = a[2];
	stiva[++top] = a[3];
	for (int i = 3; i <= n; ++i)	{
    while (top >= 3 && semn(stiva[top - 2], stiva[top - 1], stiva[top]) != 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;
}