Cod sursa(job #942939)

Utilizator harababurelPuscas Sergiu harababurel Data 23 aprilie 2013 21:10:41
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#define inf 1<<30
#define nmax 120005
#define angle first 
#define coord second
using namespace std;

struct point {
	double x, y;
};
point temp, source;

vector <pair <double, point> > p;
vector <point> S;

double polar_angle;


point top(vector <point> S) {
	return S[S.size()-1];
}
point next_to_top(vector <point> S) {
	return S[S.size()-2];
}

//if the ccw of 3 points is positive, then the segment makes a non-left turn
int ccw(point A, point B, point C) {
    return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}

int cmp(pair <double, point> a, pair <double, point> b) {
	return(a.angle <= b.angle); 
}

int main() {
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");

	int n, i, j;
	double a, b;
	temp.y = 0.0;

	f>>n;
	for(i=0; i<n; i++) {
		f>>a>>b;
		temp.x = a;
		temp.y = b;
		p.push_back(make_pair(0.0, temp));
	}

	source = p[0].coord;
	for(i=1; i<p.size(); i++) {
		if(p[i].coord.y < source.y) source = p[i].coord;
		else if(p[i].coord.y == source.y && p[i].coord.x < source.x) source = p[i].coord;
	} 

	for(i=0; i<n; i++) {
		if(p[i].coord.x == source.x && p[i].coord.y == source.y) polar_angle = -5.0;	//it's the source, so it stays first after sorting
		else polar_angle = atan2( p[i].coord.y-source.y, p[i].coord.x-source.x );
		p[i].angle = polar_angle;
	}

	sort(p.begin(), p.end(), cmp);
	//for(i=0; i<p.size(); i++) g<<p[i].coord.x<<" "<<p[i].coord.y<<": "<<p[i].angle<<"\n";
	
	S.push_back(p[0].coord);
	S.push_back(p[1].coord);
	S.push_back(p[2].coord);

	for(i=3; i<p.size(); i++) {
		while( ccw(top(S), next_to_top(S), p[i].coord) >= 0 ) S.pop_back();
		S.push_back(p[i].coord);
	}

	g<<S.size()<<"\n";

	g<<fixed;
	g<<setprecision(5);
	for(i=0; i<S.size(); i++) {
		g<<S[i].x<<" "<<S[i].y<<"\n";
	}


	return 0;
}