Cod sursa(job #2552748)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 21 februarie 2020 10:21:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
// C++
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cstdio>

using namespace std;

const int N = 12e4;
typedef double d;
typedef long double ld;

struct point{
	d first, second;

	bool operator < (const point a) const{
		if(first == a.first) return second < a.second;
		return first < a.first;
	}
}p[5 + N];

point hull[5 + N];

int n;

bool Semn(point x, point y, point z){
	return (x.first * y.second - x.second * y.first + y.first * z.second - y.second * z.first + z.first * x.second - z.second * x.first) >= 0;
}

void Compute_Hull(){
	int vf1(0), vf2(0);
	point A, B;
	point up[5 + N], down[5 + N];
	point st[5 + N];

	A = p[1];
	B = p[n];
	st[++vf1] = p[1];

	for(int i = 2; i <= n; i++){
		while(vf1 > 1 && !Semn(st[vf1 - 1], st[vf1], p[i]))
			vf1--;
		st[++vf1] = p[i];
	}

	for(int i = 1; i <= vf1; i++)
		hull[i] = st[i];
	st[++vf2] = p[n];

	for(int i = n - 1; i >= 1; i--){
		while(vf2 > 1 && !Semn(st[vf2 - 1], st[vf2], p[i]))
			vf2--;
		st[++vf2] = p[i];
	}

	for(int i = 2; i <= vf2; i++)
		hull[i + vf1 - 1] = st[i];
	vf1 += vf2 - 2;

	printf("%d\n", vf1);
	for(int i = 1; i <= vf1; i++)
		printf("%.12f %.12f\n", hull[i].first, hull[i].second);

}

int main(){
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	scanf("%d", &n);

	for(int i = 1; i <= n; i++){
		scanf("%lf%lf", &p[i].first, &p[i].second);
	}
	sort(p + 1, p + n + 1);

	Compute_Hull();
	fclose(stdin);
	fclose(stdout);
}