Cod sursa(job #2923406)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 13 septembrie 2022 12:15:07
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

#define x first
#define y second

using namespace std;

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

const int N_MAX = 12e4 + 5;

int N;
pair <double, double> v[N_MAX];

int st1[N_MAX], st2[N_MAX];

vector <pair <double, double>> Ans;

bool CheckPop(pair<double, double> A, pair<double, double> B, pair<double, double> C) {
	return ((C.y - A.y) * (B.x - A.x) - (B.y - A.y) * (C.x - A.x) <= 0);
}

void ConvexHull(int st[]) {
	int idx = 0;
	st[++idx] = 1;
	st[++idx] = 2;
	for (int i = 3; i <= N; i++) {
		while (idx > 1 && CheckPop(v[st[idx - 1]], v[st[idx]], v[i])) {
			idx--;
		}
		st[++idx] = i;
	}
	if (Ans.size() == 0) {
		for (int i = 1; i <= idx; i++) {
			Ans.push_back(v[st[i]]);
		}
	}
	else {
		for (int i = 2; i < idx; i++) {
			Ans.push_back(v[st[i]]);
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	fin.tie(NULL);
	fout.tie(NULL);

	fin >> N;
	for (int i = 1; i <= N; i++) {
		fin >> v[i].x >> v[i].y;
	}
	
	sort(v + 1, v + N + 1);
	ConvexHull(st1);
	reverse(v + 1, v + N + 1);
	ConvexHull(st2);

	fout << Ans.size() << "\n";
	for (int i = 0; i < Ans.size(); i++) {
		fout << fixed << setprecision(10) << Ans[i].x << " " << Ans[i].y << "\n";
	}
	return 0;
}