Cod sursa(job #1359022)

Utilizator danalex97Dan H Alexandru danalex97 Data 24 februarie 2015 20:58:38
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <iomanip>
using namespace std;

ifstream F("infasuratoare.in");
ofstream G("infasuratoare.out");

const int N = 120010;

struct pt {
    double x,y;
};

pt make_point(double x,double y)
{
    pt p;
    p.x = x;
    p.y = y;
    return p;
}

bool cmp(pt x,pt y)
{
    return x.x < y.x || ( x.x == y.x && x.y < y.y );
}

int ecu(pt p1,pt p2,pt p3)
{
    double a = p1.y - p2.y;
    double b = p2.x - p1.x;
    double c = - p1.y * p2.x + p1.x * p2.y;

    return ( a*p3.x + b*p3.y + c > 0 );
}

int n;
vector<pt> points,hull,stack;

void add(pt x)
{
    if ( stack.size() >= 2 )
        while ( !ecu(stack[stack.size()-2],x,stack.back()) )
        {
            stack.pop_back();
            if ( stack.size() < 2 ) break;
        }
    stack.push_back(x);
}

int main()
{
    F>>n;
    for (int i=1;i<=n;++i)
    {
        double x,y;
        F>>x>>y;
        points.push_back( make_point(x,y) );
    }

    sort(points.begin(),points.end(),cmp);
    stack.push_back( points[0] );
    for (int i=1;i<n;++i)
        if ( ecu(points[0],points[n-1],points[i]) || i == n-1 )
            add(points[i]);

    hull = stack;
    hull.pop_back();

    stack.clear();
    stack.push_back(points[n-1]);
    for (int i=n-1;i>=0;--i)
        if ( ecu(points[n-1],points[0],points[i]) || i == 0 )
            add(points[i]);
    for (int i=0;i<int(stack.size())-1;++i)
        hull.push_back(stack[i]);

    G<<hull.size()<<'\n';
    for (int i=0;i<hull.size();++i)
        G<<fixed<<setprecision(6)<<hull[i].x<<' '<<hull[i].y<<'\n';
}