Cod sursa(job #1086751)

Utilizator RobertSSamoilescu Robert RobertS Data 18 ianuarie 2014 15:02:39
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include<iostream>
#include<fstream>
#include<vector>
#include <iomanip>
using namespace std;

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

const int MAX_N = 120001;

int n;
double x[MAX_N], y[MAX_N];
double min_x, min_y;

void read(){
	fin >> n;
	
	fin >> x[1] >>  y[1];
	
	min_x  = x[1];
	min_y = y[1];
	
	for(int i=2; i<=n; i++){
		fin >> x[i] >> y[i];
		
		if(x[i] < min_x){
			min_x =  x[i];
			min_y = y[i];
		}else if(x[i] == min_x){
			if(y[i] < min_y){
				min_y = y[i];
			}
		}
	}
	
	
}

struct Point{
	double x, y;
	double tg;
};

vector<Point> list;// lista in care ordonez punctele in functie de tangenta cu punctul de coordonate (min_X, min_y)


#define pb push_back

void addToList(Point p, int li, int ls){
	if(list.size() == 0){
		list.pb(p);
	}else if(ls - li == 0){
		int lm = (li+ls)/2;
		if(list[lm].tg > p.tg){
			list.insert(list.begin() + lm , p);
		}else list.insert(list.begin()+lm+1, p);
	}else {
		int lm = (li+ls)/2;
		if(list[lm].tg < p.tg) addToList(p, lm+1, ls);
		else addToList(p, li, lm);
	}

}

void sort(){
	for(int i=1; i<=n; i++){
		if(x[i] != min_x || y[i] != min_y){
			Point p;
			p.x = x[i];
			p.y = y[i];
			p.tg = (p.y - min_y)/(p.x - min_x);
			addToList(p,0, list.size()-1);
		}
	}

}

vector<Point> st;

void solve(){
	Point p;
	p.x = min_x;
	p.y = min_y; 
	
	st.push_back(p);
	st.push_back(list[0]);
	
	// (x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)
	for(size_t i=1; i<list.size(); i++){
		size_t lung = st.size()-1;
		double x1 = st[lung-1].x;
		double y1 = st[lung-1].y;
		double x2 = st[lung].x;
		double y2 = st[lung].y;
		double x3 = list[i].x;
		double y3 = list[i].y;
		
		double res = (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
		if(res > 0) st.push_back(list[i]);
		else{
			st.pop_back();
			st.push_back(list[i]);
		}
		
	
	}
	fout << st.size() << '\n';
	fout.setf( std::ios::fixed, std:: ios::floatfield );             
	fout.precision(12);
	for(size_t i=1; i<st.size(); i++){
		fout << st[i].x <<  " " << st[i].y << '\n';
	}
	fout << st[0].x << " " << st[0].y << '\n';
	
}

int main(){
	
	read();
	sort();
	solve();

return 0;
}