Cod sursa(job #1422175)

Utilizator xoSauceSergiu Ferentz xoSauce Data 19 aprilie 2015 13:53:09
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <iomanip>
#include <algorithm>
using namespace std;

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

class point{
public:
	double x,y;
	bool operator<(const point& a) const{
		return (x < a.x || (x==a.x && y > a.y));
	}
	point(){x=y=0;}
	point(double a, double b){
		x =a;
		y = b;
	}
};

double cross_prod(point&a,point&b,point&c){
	return (b.x*c.y)+(a.x*b.y)+(c.x*a.y)-(b.x*a.y)-(b.y*c.x)-(a.x*c.y);
}
void convex_hull(std::vector<point> v){

	sort(v.begin(),v.end());
	int n = v.size();
	vector<point>l;
	vector<point>u;
	for(int i = 0,k=0; i<n;i++){
		if(k>=2){
			double value = cross_prod(l[k-2],l[k-1],v[i]);
			if(value >= 0) {
				l.pop_back();
				k--;
			}
		}
		l.push_back(v[i]);
		k++;
	}
	for(int i = v.size()-1,k=0; i>=0;i--){
		if(k>=2){
			double value = cross_prod(u[k-2],u[k-1],v[i]);
			if(value >= 0) {
				u.pop_back();
				k--;
			}
		}
		u.push_back(v[i]);
		k++;
	}
	l.pop_back();
	for(int k =0; k< u.size()-1;k++)
		l.push_back(u[k]);

	fout<<setprecision(6) << fixed;
	for(int i =l.size()-1; i >=0; i--)
		fout << l[i].x << " " << l[i].y << endl;
		
}

int main(){

	vector<point>v;
	int n;
	fin >> n;
	for(int i =0 ; i < n; i++){
		double a,b;
		fin >> a >> b;
		v.push_back(point(a,b));
	}
	convex_hull(v);
	return 0;
}