Cod sursa(job #1537249)

Utilizator sulzandreiandrei sulzandrei Data 27 noiembrie 2015 03:20:34
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 9.48 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>
#include <map>
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 = 0.00000000000000000001;

//algoritmul lent infasuratoare convexa O(n^4)
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&);

};
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;
}
bool isInside(const Point& edge,const vector<Point> &L)
{
     bool is = false;
     for(const auto& isin:L)
            if (isin == edge)
                is = true;
    return is;
}
void add(const vector<pair<Point,Point>>&E,vector<Point> &L)
{
    for(const auto& edges:E)
    {
        if(!isInside(edges.first,L))
            L.push_back(edges.first);
        if(!isInside(edges.second,L))
            L.push_back(edges.second);
    }
}
void solvesecondSlowAlg(const vector<Point>& P,vector<pair<Point,Point>>&E,bool rightOrientation)
{
    bool valid;

    for(const auto& p:P)
        for(const auto& q:P)
            if(p != q)
            {
                valid = true;
                for(const auto& r:P)
                    if( r!=p && r!=q)
                    {
                        if(rightOrientation)
                            if (r.isRight(p,q))
                                valid = false;
                        if(!rightOrientation)
                            if (r.isLeft(p,q))
                                valid = false;

                    }
                if(valid)
                    E.push_back(make_pair(p,q));
            }

}
void firstSlowAlg(const vector<Point>& P)//O(n^4)
{
    vector<Point> M;
    bool valid;
    for(const auto& p:P)
    {
        valid = true;
        for(const auto& A:P)
            for(const auto& B:P)
                for(const auto& C:P)
                    if (A!=p && B!=p && C!=p && A!=B && A!=C && B!=C)
                        if (PinsideOrEdges(p,A,B,C))
                            valid = false;
        if( valid == true)
            M.push_back(p);
    }
    Point gCen = gCenter(M);
    sort(M.begin(),M.end(),[=](const Point& A,const Point& B){return atan2(A.y-gCen.y,A.x-gCen.x)<atan2(B.y-gCen.y,B.x-gCen.x); });
    out<<M.size()<<'\n';
    for(const auto& P:M)
        out<<P;
}
void secondSlowAlg(const vector<Point>&P)//O(n^3)
{
    vector<pair<Point,Point>>E;
    vector<Point>L;
    solvesecondSlowAlg(P,E,true);
    solvesecondSlowAlg(P,E,false);
    add(E,L);
    add(E,L);
    Point gCen = gCenter(L);
    sort(L.begin(),L.end(),[=](const Point& A,const Point& B)->bool{return atan2(A.y-gCen.y,A.x-gCen.x)<atan2(B.y-gCen.y,B.x-gCen.x); });
    out<<L.size()<<'\n';
    for(const auto& p:L)
        out<<p;
}
bool anglemakesanonleftturn(Point a,Point b, Point c)
{
    return (determinant(a,b,c)<=0);
}
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 dupa unghiul polar si distanta polara
    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 (a.pa<b.pa);});
    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;
}
void Jarvis_March( vector<Point>& P)
{
    Point p0(1000000000,1000000000);
    for( auto &p:P)
        if(p.y<p0.y)
                p0 = p;
        else
            if(p.y == p0.y)
                if( p.x < p0.x)
                    p0 = p;
    vector<Point> L;
    vector<Point>::iterator it2,rp;
    Point lp;
    L.push_back(p0);
    while(true)
    {
        lp = L.back();
        rp = P.begin();
        for(auto it = P.begin()+1; it!= P.end() ;it++)
            if( it-> isRight(lp, *rp) || it -> isOn(lp, *rp) )
                if (it->isRight(lp,*rp))
                    rp = it;
                else
                    rp = (lp.distanceFrom(*rp)>lp.distanceFrom(*it))?rp:it;

        if (*rp == p0)
            break;
        L.push_back(*rp);
        P.erase(rp);
    }
    out<<L.size()<<'\n';
    for(const auto &p :L)
        out<<p;
}
int main()
{
    int n;
    in>>n;
    Point p;
    vector<Point> P;

    foreach(i,n)
    {
        in>>p;
        P.push_back(p);
    }
    int op=4;
    //cout<<"1-FirstSlowAlg\n2-SecondSlwAlg\n3-Grahams Scan\n4-Jarvis'March\n";
    //cin>>op;
    switch(op)
    {
        case 1: firstSlowAlg(P); return 0;
        case 2: secondSlowAlg(P); return 0;
        case 3: Grahams_Scan_Convex_Hull(P); return 0;
        case 4: Jarvis_March(P); return 0;
    }
    return 0;
}