Cod sursa(job #1581315)

Utilizator sulzandreiandrei sulzandrei Data 26 ianuarie 2016 18:51:11
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 3.92 kb
//algoritmi sunt implementati bazandu-ma pe pseudocodul de aici http://gta.math.unibuc.ro/stup/geom_comp.pdf
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
#include <deque>
#include <algorithm>
#include <stack>
#include <iomanip>
using namespace std;

#define foreach(i,n) for(int i = 0; i < n ; i++)

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

const long double epsilon = 10e-15;

//algoritmul lent infasuratoare convexa O(n^4)c
struct Point
{
   long double x,y,pa,pd;
   Point(){x = 0; y = 0; pa= 0; pd  = 0;}
   Point(long double xx,long double yy){ x = xx; y = yy; pa=  0 ; pd= 0 ;}

   friend               istream& operator >>(   istream& i , Point& p   );
   friend               ostream& operator <<(   ostream& o, Point&p );
   friend               ostream& operator<<(    ostream&o, const Point& p   );

   bool                 operator != (   const Point& B  );
   bool                 operator != (   const Point& B  )const;
   bool                 operator ==(    const Point&B   )const;
   Point                operator /=(    long double divide  );
   Point                operator +=(    const Point&    );

};
bool  orientation( Point p0,Point p1, Point p2)
{
    Point p1prim,p2prim;
    p1prim.x = p1.x - p0.x;
    p1prim.y = p1.y - p0.y;
    p2prim.x = p2.x - p0.x;
    p2prim.y = p2.y - p0.y;
    return (p1prim.x * p2prim.y - p2prim.x * p1prim.y >= 0);//p1 in dreapta lu p2
}
Point Point::operator +=(const Point& B)
{
    x += B.x;
    y += B.y;
    return *this;
}
Point Point::operator /=(long double divide)
{
    x /= divide;
    y /= divide;
    return *this;
}
bool Point::operator !=(const Point& B)
{
    if (x == B.x && y == B.y)
        return false;
    return true;
}
bool Point::operator ==(const Point&B)const
{
    if( x == B.x && y == B.y)
        return true;
    return false;
}
bool Point::operator !=(const Point& B)const
{
    if (x == B.x && y == B.y)
        return false;
    return true;
}
istream& operator>>(istream& i , Point& p)
{
    i >> p.x >> p.y;
    return i;
}
ostream& operator<<(ostream& o , Point&p)
{
    o<< fixed << setprecision(2) << p.x<< " "<< fixed << setprecision(2) <<p.y;
    return o;
}
ostream& operator<<(ostream&o,const Point& p)
{
    o<<fixed<<setprecision(6)<<p.x<<" "<<fixed<<setprecision(6)<<p.y<<'\n';
    return o;
}
void Grahams_Scan_Convex_Hull(vector<Point>&P2)
//O(nlogn) here is a good example+pseudocod https://www.youtube.com/watch?v=QYrpHE8iDGg
//also we can test here https://www.mathsisfun.com/data/cartesian-coordinates-interactive.html
{
    //sortam punctele
    Point p0(1000000000,1000000000);
    stack<Point> s;
    for( auto &p:P2)
        if(p.y<p0.y)
                p0 = p;
        else
            if(p.y == p0.y)
                if( p.x < p0.x)
                    p0 = p;
    vector<Point>P;
    for(auto it = P2.begin() ; it!=P2.end() ; it++)
        if ( *it != p0)
        {
            P.push_back(*it);
        }
    sort(P.begin(),P.end(),[=](Point a,Point b)->bool{ return orientation(p0,a,b);});

   auto it = P.begin();
   s.push(p0);
   s.push(*it);
   s.push(*(it+1));
   Point p1,p2,pi;

   for(auto p = it+3; p!=P.end() ; p++)
   {
       pi = *p;
       p2 = s.top();
       s.pop();
       p1 = s.top();
       s.push(p2);
       while( !orientation(p1,p2,pi))
       {
           s.pop();
           p2 = p1;
           s.pop();
           p1 = s.top();
           s.push(p2);
       }

       s.push(pi);
   }
   deque<Point> dP;
   while(!s.empty())
   {
       dP.push_front(s.top());
       s.pop();
   }

   out<<dP.size()<<'\n';

   for(const auto& it:dP)
       out<<it;
}

int main()
{
    int n;
    in>>n;
    Point p;
    vector<Point> P;

    foreach(i,n)
    {
        in>>p;
        P.push_back(p);
    }
    Grahams_Scan_Convex_Hull(P);
    return 0;
}