Cod sursa(job #2656524)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 7 octombrie 2020 21:43:39
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define e 1e-12


vector<pair<float, float>> points;

double crossProduct(pair<float, float> & a, pair<float, float> &b, pair<float, float> & c) {
	return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}

int comp(pair<float, float> a, pair<float, float> b) {
	return crossProduct(points[0], a, b) < 0;
}


int main() {
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);

	int n, minIndex = 0;
	float x, y, aux;
	scanf("%d", &n);
	points.resize(n);

	for (int i=0; i<n; ++i) {
		scanf("%f%f", &x, &y);
		points[i].first = x;
		points[i].second = y;

		if (x - points[minIndex].first < e && x - points[minIndex].first > -e && y < points[minIndex].second)
			minIndex = i;
		else
			if (x < points[minIndex].first)
				minIndex = i;
	}

	if (minIndex != 0) {
		aux = points[minIndex].first;
		points[minIndex].first = points[0].first;
		points[0].first = aux;

		aux = points[minIndex].second;
		points[minIndex].second = points[0].second;
		points[0].second = aux;
	}

	sort(points.begin() + 1, points.end(), comp);

	vector<int> st;
	st.push_back(0);
	st.push_back(1);

	for(int i=2; i<n; ++i) {
		while(st.size() >= 2 && crossProduct(points[st[st.size() - 2]], points[st[st.size() - 1]], points[i]) > 0) {
			st.pop_back();
		}
		st.push_back(i);
	}

	printf("%d\n", st.size());
	for(int i=st.size() -1 ; i>=0; --i)
		printf("%6f %6f\n", points[st[i]].first, points[st[i]].second);

	return 0;
}