Cod sursa(job #1110905)

Utilizator fhandreiAndrei Hareza fhandrei Data 18 februarie 2014 14:38:36
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
// Include
#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
 
// Definitii
#define point_t pair<double, double>
#define y first
#define x second
 
#define pb push_back
#define popb pop_back
 
#define prev at(convexHull.size()-2)
#define top at(convexHull.size()-1)
 
// Constante
const int sz = (int)12e4+1;
 
// Functii
bool leftTurn(point_t a, point_t b, point_t c);
bool byAngle(point_t a, point_t b);
 
// Variabile
int num;
 
point_t minPoint;
 
point_t points[sz];
 
vector<point_t> convexHull;
 
// Main
int main()	
{
	freopen("infasuratoare.in", "rt", stdin);
	freopen("infasuratoare.out", "wt", stdout);
	
	scanf("%d", &num);
	//in >> num;
	scanf("%lf%lf", &minPoint.x, &minPoint.y);
	//in >> minPoint.x >> minPoint.y;
	 
	for(int i=1 ; i<num ; ++i)
	{
		scanf("%lf%lf", &points[i].x, &points[i].y);
		if(points[i] < minPoint)
			swap(points[i], minPoint);
	}
	 
	sort(points+1, points+num, byAngle);
	 
	convexHull.reserve(num);
	 
	convexHull.pb(minPoint);
	convexHull.pb(points[1]);
	 
	for(int i=2 ; i<num ; ++i)
	{
		while(!leftTurn(convexHull.prev, convexHull.top, points[i]))
			convexHull.popb();
		convexHull.pb(points[i]);
	}
	 
	printf("%d\n", convexHull.size());
	 
	vector<point_t>::iterator it, end=convexHull.end();
	for(it=convexHull.begin() ; it!=end ; ++it)
		printf("%lf %lf\n", it->x, it->y);
	 
	fclose(stdin);
	fclose(stdout);
	return 0;
}
 
bool leftTurn(point_t a, point_t b, point_t c)
{   return (a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x) >= 0; }
 
bool byAngle(point_t a, point_t b)
{   return leftTurn(minPoint, a, b) > 0; }