Cod sursa(job #963649)

Utilizator gener.omerGener Omer gener.omer Data 17 iunie 2013 22:54:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

struct Point
{
    double x, y;
};

Point vp[120005], st[120005];

int N;

double x_prod(const Point& A, const Point& B, const Point& C)
{
	return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

bool cmp(const Point& p1, const Point& p2)
{
    return x_prod(vp[0], p1, p2) > 0;
}

int main()
{
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");
    
    in >> N;
	
    for(int i = 0; i < N; ++i)
    {
        in >> vp[i].x >> vp[i].y;
    }
	
    int minp = 0;
	
    for(int i = 1; i < N; ++i)
    {
        if((vp[i].y < vp[minp].y) || (vp[i].y == vp[minp].y && vp[i].x < vp[minp].x))
        {
            minp = i;
        } 
    }
	

	swap(vp[0], vp[minp]);
	
    sort(vp + 1, vp + N, cmp); 
	
	st[0] = vp[0];
	st[1] = vp[1];
		
	int last = 1;
	
	for(int i = 2; i < N; ++i)
	{
		while(last >= 1 && x_prod(st[last - 1], st[last], vp[i]) < 0)
			--last;
		st[++last] = vp[i]; 
	}
	
	out << last + 1 << endl;
	
	out << fixed;
	out << setprecision(6) << st[0].x << " " << st[0].y << endl;
	
	for(int i = 1; i <= last; ++i)
	{
		out << setprecision(6) << st[i].x << " " << st[i].y << endl;
	}
    
    return 0;
}