Cod sursa(job #964978)

Utilizator DantePlop Daniel Dante Data 22 iunie 2013 21:01:36
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 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;
		}
	}
	swap(points[0],min);
	sort(points+1, points+N, cmp);

	stive.push_back(points[0]);
	stive.push_back(points[1]);
	
	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]);
	}
	g<<stive.size()<<endl;
	for(int i = lng; i>=0; --i)
		g<<setprecision(9)<<stive[i].x<<" "<<stive[i].y<<" "<<endl;
	g.close();

    return 0;
}