Cod sursa(job #1962532)

Utilizator DoubleNyNinicu Cristian DoubleNy Data 11 aprilie 2017 20:54:52
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;
typedef pair<double, double> point;
point arr[120120]; 
point ans[120120]; 
int n;

float 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 sortare(){
		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(){
		//freopen("input.in", "r", stdin);
		freopne("infasuratoare.in", "r", stdin);
		freopne("infasuratoare.out", "w", stdout);
		scanf("%d", &n);
		for(int i=0;i<n;i++)
			scanf("%lf%lf", &arr[i].first, &arr[i].second);
		sortare();
		ans[0] = arr[0];
		ans[1] = arr[1];
		int elem = 1;
		for(int i=2;i<=n;i++){
			while(det(ans[elem-1], ans[elem], arr[i]) > 0 && elem > 0)
				elem--;
			ans[elem+1] = arr[i];
			elem++;
		}
		printf("%d\n", elem);
		for(int i=elem-1;i>-1;i--)
			printf("%lf %lf\n", ans[i].first, ans[i].second);
}