Cod sursa(job #964971)

Utilizator DantePlop Daniel Dante Data 22 iunie 2013 20:42:24
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

struct Point
{
    double x, y;
};

Point points[120005];
vector<Point> stive;

#define inf 1000000005.0
#define lng stive.size()-1
int N;

double dot_product(Point P0, Point P1, Point P2)
{
	return (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y);
}

bool cmp(Point P1, Point P2)
{
	return dot_product(points[0],P1,P2) < 0;
}

int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    
    f >> N;
	
    for(int i = 0; i < N; ++i)
    {
        f >> points[i].x >> points[i].y;
    }

	Point min;
	min.x = 1000000005.0;
	min.y = 1000000005.0;
	for(int i = 0; i < N; ++i)
	{
		if( points[i].y < min.y || ( points[i].y == min.y && points[i].x < min.x))
		{
			min.x = points[i].x;
			min.y = points[i].y;
		}
	}
	cout<<"Minimum:"<<min.x<<" "<<min.y<<endl;

	swap(min,points[0]);

	sort(points+1, points+N, cmp);

	for(int i = 0; i< N;i++)
		cout<<"X: "<<points[i].x<<" "<<"Y: "<<points[i].y<<" "<<endl;
		cout<<"----------------------------------------------"<<endl;

	stive.push_back(points[0]);
	stive.push_back(points[1]);
	//stive.push_back(points[2]);

	for(int i = 0; i< stive.size(); i++)
		cout<<"X: "<<stive[i].x<<" "<<"Y: "<<stive[i].y<<" "<<endl;
		cout<<"----------------------------------------------"<<endl;

	for( int i=2; i<N; i++)
	{
		while(stive.size() > 1 && dot_product(stive[lng-1], stive[lng], points[i]) > 0)
		{
			stive.pop_back();
		}
		stive.push_back(points[i]);
	}
	cout<<"size: "<<stive.size()<<endl;

	for(int i = 0; i<=lng; ++i)
		cout<<"X: "<<stive[i].x<<" "<<"Y: "<<stive[i].y<<" "<<endl;
		cout<<"-----------------------------------------------------"<<endl;

	for(int i = lng; i>=0; --i)
		cout<<"X: "<<stive[i].x<<" "<<"Y: "<<stive[i].y<<" "<<endl;

    return 0;
}