Cod sursa(job #966450)

Utilizator DantePlop Daniel Dante Data 25 iunie 2013 22:00:41
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
 
using namespace std;

#define inf 1000000005
typedef struct 
{
    double x, y;
} Point;

vector<Point>points;
vector<Point> stive;
long N;
Point p;

double cross_prod(Point A, Point B, Point C )
{
	return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
bool comp(Point A, Point B)
{
	if(cross_prod(points[0], A, B) <= 0)
		return false;
	else
		return true;
}

 
int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
     
    f >> N;
	//read from file
	for(long i=1; i<=N; i++)
	{
		f >> p.x >> p.y;
		points.push_back(p);
	}
	//find minimum
	Point min;
	min.x=inf;
	min.y=inf;
	for(size_t i=0; i<points.size(); i++)
	{
		if(points[i].y < min.y)
		{
			min.y = points[i].y;
			min.x = points[i].x;
		}
		else if(points[i].y == min.y)
		{
			if(points[i].x < min.x)
			{
				min.y = points[i].y;
				min.x = points[i].x;
			}
		}
		else
			continue;
	}
	//make minimum first element for graham scan
	swap(min,points[0]);

	//sort elements acording to the polar angle with respect to first point
	vector<Point>::iterator it = points.begin();
	++it;
	sort(it, points.end(), comp);

	stive.push_back(points[0]);
	stive.push_back(points[1]);
	stive.push_back(points[2]);
	//grahams scan
	for(size_t i=3; i<points.size(); i++)
	{
		while(cross_prod(stive[stive.size()-2], stive[stive.size()-1],points[i]) < 0)
		{
			stive.pop_back();
		}
		stive.push_back(points[i]);
	}

	g<<fixed<<stive.size()<<endl;
	for(size_t i=0; i<stive.size(); i++)
	{
		g<<setprecision(6);
		g<<stive[i].x <<" "<<stive[i].y<<endl;
	}
	g.close();
    return 0;
}