Cod sursa(job #965028)

Utilizator DantePlop Daniel Dante Data 22 iunie 2013 23:31:30
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 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(dot_product(stive[lng-1], stive[lng], points[i]) > 0)
        {
            stive.pop_back();
        }
        stive.push_back(points[i]);
    }
	g<<fixed<<stive.size()<<endl;
	for(int i=lng; i>=0; i--)
        g<<setprecision(9)<<stive[i].x<<" "<<stive[i].y<<" "<<endl;
 
    return 0;
}