Cod sursa(job #1581247)

Utilizator sulzandreiandrei sulzandrei Data 26 ianuarie 2016 17:56:39
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 6.57 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&    );

   long double          distanceFrom(   const Point &B  );
   long double          distanceFrom(   const Point &B  )const;

   bool                 isRight(    const Point &A, const Point& B  )const;
   bool                 isLeft( const Point &A, const Point& B   )const;
   bool                 isOn(   const Point &A, const Point& B )const;

   long double          polarAngle(     const Point& p0     );
   long double          polarDistance(      const Point& p0  );
   bool            orientation( Point p0,Point p1, Point p2);

};
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);
}
long double Point::polarAngle(const Point& p0)
{
    return atan2((long double)(y-p0.y),(long double)(x-p0.x));
}
long double Point::polarDistance(const Point& p0)
{
    return sqrt( (  x-p0.x  )*( x - p0.x ) + ( y - p0.y )*( y - p0.y ) );
}
long double determinant(const Point&P, const Point& Q, const Point&R)
{
    return ( Q.x * R.y + P.x * Q.y + R.x * P.y - Q.x * P.y - R.x * Q.y - P.x * R.y);
}
bool Point::isRight(const Point &A, const Point& B)const
{
    return ( determinant(A, B, *this)<0);
}
bool Point::isOn(const Point &A, const Point& B)const
{
    return ( determinant(A, B, *this) == 0);
}
bool Point::isLeft(const Point &A, const Point& B)const
{
     return (determinant(A, B, *this) > 0);
}
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;
}
Point gCenter(const vector<Point>& M)
{
    Point p;

    for(const auto& point:M)
        p += point;

    p /=M.size();

    return p;
}
long double area( const Point& A, const Point& B, const Point& C)
{
    return abs((1.0/2.0)*( A.x * B.y + B.x * C.y + A.y * C.x - B.y * C.x - A.x * C.y - A.y * B.x));
}
long double Point::distanceFrom(const Point& B)
{
    return abs( sqrt( (B.x - x ) * ( B.x - x) + (B.y - y) * (B.y - y) ));
}
long double Point::distanceFrom(const Point& B)const
{
    return abs(sqrt( (B.x - x ) * ( B.x - x ) + ( B.y - y) * ( B.y - y) ));
}
bool PinsideOrEdges(const Point& p, const Point& A, const Point& B, const Point& C)
{
    bool value = false;
    if ( abs((area(A,B,C)- (area(p,A,B)+area(p,A,C)+area(p,B,C)) )) <epsilon)
        value = true;
    if ( abs( A.distanceFrom(B) - (A.distanceFrom(p) + p.distanceFrom(B) ) ) <epsilon && p!=A && p!= B)
        value = true;
    if ( abs(A.distanceFrom(C) - (A.distanceFrom(p) + p.distanceFrom(C) ) ) <epsilon && p!=A && p!= C)
        value = true;
    if ( abs(B.distanceFrom(C) - (B.distanceFrom(p) + p.distanceFrom(C) ) ) <epsilon && p!=B && p!= C)
        value = true;
    return value;
}
void Grahams_Scan_Convex_Hull(vector<Point>&P)
//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:P)
        if(p.y<p0.y)
                p0 = p;
        else
            if(p.y == p0.y)
                if( p.x < p0.x)
                    p0 = p;

    for(auto p = P.begin();p!=P.end(); p++)
    {
        p->pa = p->polarAngle(p0);
        p->pd = p->polarDistance(p0);
    }
    sort(P.begin(),P.end(),[=](Point a,Point b)->bool{ return orientation(p0,a,b);});

    for(auto it = P.begin() ; it!=P.end() ; it++)
        if( it+1 !=P.end() && abs( abs(it->pa)-abs( (it+1)->pa))<= epsilon)
            if(it->pd>(it+1)->pd)
                P.erase(it+1);
            else
                P.erase(it);

   auto it = P.begin();
   s.push(*it);
   s.push(*(it+1));
   s.push(*(it+2));
   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( pi.isRight(p1,p2) || pi.isOn(p1,p2))
       {
           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;
}