Cod sursa(job #1422666)

Utilizator xoSauceSergiu Ferentz xoSauce Data 19 aprilie 2015 15:49:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <iomanip>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

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

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

double cross(const point& a, const point& b, const 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(vector<point>& v){

	sort(v.begin(),v.end());
	int n = v.size();
	vector<point>l(2*n);
	int k =0;
	for(int i = 0; i < v.size(); i++){
		while(k>=2 && cross(l[k-2],l[k-1],v[i]) <=0)
			k--;
		l[k++] = v[i];
	}
	int l_size =k;
	vector<point>u(2*n);
	k = 0;
	for(int i = v.size()-1; i>=0; i--){
		while(k>=2 && cross(u[k-2],u[k-1],v[i]) <=0)
			k--;
		u[k++] = v[i];
	}
	int u_size = k;
	fout<<setprecision(6)<<fixed;
	fout << l_size + u_size-2 << endl;
	for(int i = 0; i < l_size; i++){
		fout << l[i].x << " " << l[i].y << endl;
	}
	for(int i = 1; i < u_size-1; i++){
		fout << u[i].x << " " << u[i].y << endl;
	}
}

int main(){
	int N;
	fin >> N;
	vector<point> v;
	for(int i =0 ; i < N; i++){
		double x,y;
		fin >> x >> y;
		v.push_back(point(x,y));
	}
	convex_hull(v);

}