Cod sursa(job #1110898)

Utilizator fhandreiAndrei Hareza fhandrei Data 18 februarie 2014 14:33:17
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
// Include
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;
 
// Definitii
#define pb push_back
#define popb pop_back
 
#define point pair<double, double>
#define y first
#define x second
 
#define leftTurn(a, b, c) (det(a, b, c) > 0)
 
#define prev at(convexHull.size()-2)
#define current at(convexHull.size()-1)
 
// Constante
const int sz = (int)12e4+1;
 
// Functii
double det(point a, point b, point c);
class byAngle
{   public: bool operator()(point a, point b);  };
 
// Variabile
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
 
int num;
point minPoint;
point points[sz];
 
vector<point> convexHull;
 
// Main
int main()
{
    out << fixed << setprecision(6);
    in >> num;
    in >> minPoint.x >> minPoint.y;
     
    for(int i=1 ; i<num ; ++i)
    {
        in >> points[i].x >> points[i].y;
        if(points[i] < minPoint)
            swap(points[i], minPoint);
    }
     
    sort(points+1, points+num, byAngle());
     
    convexHull.pb(minPoint);
    convexHull.pb(points[1]);
     
    for(int i=2 ; i<num ; ++i)
    {
        while(!leftTurn(convexHull.prev, convexHull.current, points[i]))
            convexHull.popb();
        convexHull.pb(points[i]);
    }
     
    out << convexHull.size() << '\n';
     
    vector<point>::iterator it, end=convexHull.end();
    for(it=convexHull.begin() ; it!=end ; ++it)
        out << it->x << ' ' << it->y << '\n';
     
    in.close();
    out.close();
    return 0;
}
 
bool byAngle::operator()(point a, point b)
{   return leftTurn(minPoint, a, b);    }
 
double det(point a, point b, point c)
{   return a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x;   }