Cod sursa(job #3141707)

Utilizator antoniadutuDutu Antonia antoniadutu Data 15 iulie 2023 19:21:44
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, viz[10001];
struct coord {
	long double x, y;
} v[10001], S[10001], D[10001];

bool cmp (coord a, coord b) {
	if (a.x > b.x) {
		return 0;
	}

	if (a.x == b.x) {
		if (a.y > b.y) {
			return 0;
		}

		return 1;
	}

	return 1;
}

int main () {

	fin >> n;

	for (int i = 1; i <= n; i++) {
		fin >> v[i].x >> v[i].y;
	}

	sort(v + 1, v  + 1 + n, cmp);

	int cnt = 2;

	S[1].x = v[1].x;
	S[1].y = v[1].y;
	S[2].x = v[2].x;
	S[2].y = v[2].y;

	for (int i = 3; i <= n; i++) {
		//punctul A : S[cnt -1].x, S[cnt - 1].y
		//punctul B : S[cnt].x, S[cnt].y
		//punctul C : v[i].x, v[i].y

		while (cnt >= 2 && (v[i].y - S[cnt - 1].y) * (S[cnt].x - S[cnt - 1].x) - (S[cnt].y - S[cnt - 1].y) * (v[i].x - S[cnt - 1].x) < 0) {
			cnt--;
		}

		cnt++;
		S[cnt].x = v[i].x;
		S[cnt].y = v[i].y;
	}	

	int cnt2 = 2;
	
	D[1].x = v[n].x;
	D[1].y = v[n].y;
	D[2].x = v[n - 1].x;
	D[2].y = v[n - 1].y;

	for (int i = n - 2; i >= 1; i--) {
		//punctul A : D[cnt -1].x, D[cnt - 1].y
		//punctul B : D[cnt].x, D[cnt].y
		//punctul C : v[i].x, v[i].y

		while (cnt2 >= 2 && (v[i].y - D[cnt2 - 1].y) * (D[cnt2].x - D[cnt2 - 1].x) - (D[cnt2].y - D[cnt2 - 1].y) * (v[i].x - D[cnt2 - 1].x) < 0) {
			cnt2--;
		}

		cnt2++;
		D[cnt2].x = v[i].x;
		D[cnt2].y = v[i].y;
	}	

	fout << cnt + cnt2 - 2 << '\n';

	for (int i = 1; i <= cnt; i++) {
		fout << fixed << setprecision(6) << S[i].x << " " << S[i].y << '\n';
	}

	for (int i = 1; i <= cnt2; i++) {
		if (D[i].x == v[1].x && D[i].y == v[1].y) {
			continue;
		} else if (D[i].x == v[n].x && D[i].y == v[n].y) {
			continue;
		} else {
			fout << fixed << setprecision(6) << D[i].x << " " << D[i].y << '\n';
		}
	}

	return 0;
}