Cod sursa(job #1091933)

Utilizator RobertSSamoilescu Robert RobertS Data 26 ianuarie 2014 11:59:49
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;

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

const int MAX_N = 120001;

int n, index=0;
double min_x, min_y;


struct Point{
	double x, y;
	double tg;
}p[MAX_N];

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



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



bool cmp(Point p1, Point p2){
	p1.tg = (p1.y - min_y)/(p1.x - min_x);
	p2.tg = (p2.y - min_y)/(p2.x - min_x);
	
	return p1.tg < p2.tg;
}



#define pb push_back

vector<Point> st;

void solve(){
	swap(p[index],p[1]);
	sort(p+2,p+n+1,cmp);
	
	
	st.push_back(p[1]);
	st.push_back(p[2]);
	
	// (x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)
	for(int i=3; i<n+1; 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 = p[i].x;
		double y3 = p[i].y;
		
		double res = (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
		if(res > 0) st.push_back(p[i]);
		else{
			st.pop_back();
			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();
	solve();

return 0;
}