Cod sursa(job #387084)

Utilizator ChallengeMurtaza Alexandru Challenge Data 26 ianuarie 2010 19:59:19
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
//Graham scan in O(NlogN)
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>

using namespace std;

const char InFile[]="infasuratoare.in";
const char OutFile[]="infasuratoare.out";
const char RMode[]="r";
const char WMode[]="w";
const long int MaxN=10005;
const double PI=3.1415926536;

struct p2d{
	double x,y;
};

vector<p2d> p,c;
p2d t;
long int n;
FILE *f;
ifstream fin(InFile);
ofstream fout(OutFile);

double PolarAngle(p2d P, p2d Q){
	double angle=atan2(Q.y-P.y,Q.x-P.x);
	if(angle<0){
		angle+=PI*2;
	}
	return angle;
}

typedef  pair<p2d, double> polar_point;

bool polar_point_cmp(const polar_point& left, const polar_point& right){
	return left.second<right.second;
}

inline double det(p2d p1, p2d p2, p2d p3){
	return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}

inline bool good(p2d p1, p2d p2, p2d p3){
	return det(p1,p2,p3)>0;
}

int main(){
	f=fopen(InFile,RMode);
	fscanf(f,"%ld",&n);
	fin>>n;
	for(register int i=0;i<n;++i){
		fin>>t.x>>t.y;
		p.push_back(t);
	}
	fin.close();
	
	p2d ext;
	int ind=0;
	ext=p[0];
	for(register long int i=1;i<(long int)p.size();++i){
		if(ext.y>p[i].y || (ext.y==p[i].y && ext.x>p[i].x)){
			ext=p[i];
			ind=i;
		}
	}
	p.erase(p.begin()+ind);
	c.push_back(ext);
	
	vector<polar_point> s;
	for(register long int i=0;i<(long int)p.size();++i){
		s.push_back(polar_point(p[i],PolarAngle(c[0],p[i])));
	}
	sort(s.begin(),s.end(),polar_point_cmp);
	
	c.push_back(s[0].first);
	c.push_back(s[1].first);
	for(register long int i=2;i<(long int)s.size();++i){
		p2d p_i=s[i].first;
		p2d p_i1=c[c.size()-1];
		p2d p_i2=c[c.size()-2];
		while(!good(p_i2,p_i1,p_i)){
			c.erase(c.end()-1);
			p_i1=p_i2;
			p_i2=c[c.size()-2];
		}
		c.push_back(p_i);
	}
	
	fout<<c.size()<<"\n";
	for(register long int i=0;i<(long int)c.size();++i){
		fout<<setprecision(6)<<c[i].x<<" "<<c[i].y<<"\n";
	}
	fout.close();
	return 0;
}