Cod sursa(job #2211526)

Utilizator primeBasso Nicolae prime Data 10 iunie 2018 19:41:14
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

int i, n, s = 1, k = 2;

struct point{
	double x, y;
}p[120010], ans[120010];

bool det(point a, point b, point c){
	return (a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - c.y * a.x - a.y * b.x > 0);
}

bool cmp(point a, point b){
	return det(p[1], a, b);
}

int main(){
	ifstream cin("infasuratoare.in");
	ofstream cout("infasuratoare.out");
	
	cin >> n;
	
	for(i = 1; i <= n; i++){
		cin >> p[i].x >> p[i].y;
		
		if(p[i].x < p[s].x || (p[i].x == p[s].x && p[i].y < p[s].y))
			s = i;
	}
	
	swap(p[1], p[s]);
	sort(p + 2, p + n + 1, cmp);
	
	ans[1] = p[1];
	ans[2] = p[2];
	
	for(i = 3; i <= n; i++){
		while(!det(ans[k - 1], ans[k], p[i]))
			k--;
		
		ans[++k] = p[i];
	}
	
	cout << k << "\n" << fixed << setprecision(12);
	
	for(i = 1; i <= k; i++)
		cout << ans[i].x << " " << ans[i].y << "\n";
	
	return 0;
}