Cod sursa(job #1806719)

Utilizator DoubleNyNinicu Cristian DoubleNy Data 15 noiembrie 2016 17:27:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;
//struct point{
//	double x, y;
//};

typedef pair<double, double> point;
point arr[120001];
int n;
double det(point a, point b, point c){
	    return(a.first * b.second) + (b.first * c.second) + (c.first * a.second) - (b.second * c.first)-
			  (c.second * a.first) - (a.second * b.first);
}

int criteria(const point& a, const point& b){
		if(det(arr[0], a, b) < 0)
			return(1);
		return(0);
}

void Sort0(){
		int k = 0;
		for(int i = 1; i < n; i++)
			if(arr[i] < arr[k])
				k = i;
		swap(arr[0], arr[k]);
		sort(arr + 1, arr + n, criteria);
}

int main(){
			ifstream cin("infasuratoare.in");
			//ifstream cin("input.in");
			ofstream cout("infasuratoare.out");			
			cin >> n;
			for(int i = 0; i < n; i++)
					cin >> arr[i].first >> arr[i].second;
			Sort0();
			point st[120001];
				  st[0] = arr[0];
				  st[1] = arr[1];
			int elem = 1;
			for(int i = 2; i<= n; i++){
					while(det(st[elem - 1] , st[elem] , arr[i]) > 0 && elem > 0)
							elem--;
					st[elem + 1] = arr[i];
					elem++;
			}
			cout << elem << endl;
			for(int i = elem - 1; i > -1; i--)
				cout << fixed << setprecision(10) << st[i].first << ' ' << st[i].second << endl;
}