Выпуклая оболочка - C++ - Ответ 35208

// Pol.cpp : Defines the entry point for the console application.
//
 
//#include "stdafx.h"
#include <iostream.h>
#include <math.h>
 
//Klass, opisyvauchiy tochku (Point) na ploskosti (R2)
class  R2Point 
{
    double x,y;
public:
    R2Point(double a, double b)
       {
      x=a; y=b;
       }; 
    R2Point()
       {
       x=0;  
       y=0;  
       };
    double dist(R2Point a, R2Point b)
       {
       return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
       };
    double area(R2Point a, R2Point b, R2Point c)
       {
       double s= 0.5*((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x));
       return (s);
       };
    int equal(R2Point a, R2Point b)
       {
       return (a.x==b.x && a.y==b.y);
       };
    int isTriangle(R2Point a, R2Point b, R2Point c)
       {
       return (area(a, b, c) != 0.0);
       };
    int inside(R2Point a, R2Point b)
       {
       return ((a.x <= x && x <= b.x || a.x >= x && x >= b.x) &&
             (a.y <= y && y <= b.y || a.y >= y && y >= b.y));
       };
    int light(R2Point a, R2Point b)
       {
       double s=area(a, b, *this);
       return (s < 0.0 || (s == 0.0 && ! inside(a, b)));
       };
};
 
//Nepreryvnaya realizaciya deka
class Deq
{     
//private final static int DEFSIZE = 16;
       R2Point array[16];
      int size, head, tail;
      int forward (int index)
       {
       return (++index <16 ? index : 0); 
       };
      int backward (int index)
       {
       return (--index >=0 ? index : 15);
       };
     public: Deq (int razmer)
       {
       size=head=0;
       tail=15;
       };
     public: Deq()
       {
       size=head=0;
       tail=15;
       };
     public: int length()
       {
       return (size);
       };
     public: void pushFront(R2Point p)
       {
       array[head=backward(head)]=p;
       size +=1;
       };
     public: void pushBack(R2Point p)
       {
      array[tail=forward(tail)]=p;
       size +=1;
       };
     public: R2Point popFront()
       {
       R2Point p=front();
       head=forward(head);
       size -=1;
       return (p);
       };
     public: R2Point popBack()
       {
       R2Point p=back();
       tail=backward(tail);
       size -=1;
       return (p);
       };
     public: R2Point front()
       {
       return (array[head]);
       };
     public: R2Point back()
       {
       return (array[tail]);
       };
};
 
//Klass, zadaushiy novyi tip - Figure
class Figure
{
    public: virtual double area()
            {return (0.0);};
    public: virtual double perimeter()
            {return (0.0);};
    public: virtual Figure *add(R2Point p)
            {return this;};
};
 
//Klass "mnogo-ugolnik"
class Polygon: public Figure, public Deq
{
      double s,p;
 
    private: void grow(R2Point a, R2Point b, R2Point t)
       {
      p -= a.dist(a,b);
       s += fabs(t.area(a,b,t));
       };
 
    public: Polygon (R2Point a, R2Point b, R2Point c)
            {
     pushFront(b);
    if (b.light(a,c))
           {
            pushFront(a); pushBack(c); 
           }  else 
              {
              pushFront(c); pushBack(a);
              };
       p=a.dist(a,b) + b.dist(b,c) + c.dist(c,a);
       s=fabs(a.area(a,b,c));
       };
 
    public: double area()
       {
       return s;
       };
    public: double perimeter()
       {
       return p;
       };
//////////////////////////////
    public: Figure *add(R2Point t)
      {
       int i;
//Ischem osveschennye rebra
       for (i=length(); i>0 && !t.light(back(),front()); i--)
           pushBack(popFront());
//UTVERGDENIE: libo rebro [back(),front()); osvesheno iz t,
//             libo osveshennych reber net sovsem.
//
           if (i>0) {
                R2Point x;
                grow(back(),front(),t);
           // Udalaem vse osveshennye rebra iz nachala deka
                for (x=popFront(); t.light(x,front()); x=popFront())
                grow(x,front(),t);   
                pushFront(x);
           //Udalaem vse osveshennye rebra iz konca deka
                for (x=popBack(); t.light(back(),x); x=popBack())
                grow(back(),x,t);    
                pushBack(x);
          //Zavershaem obrabotku dobavlaemoi tochki
                p+=t.dist(back(),t)+t.dist(t,front());
                pushFront(t);   
                };
       return this;
       };
};
 
//Klass - "Dvu-ugolnik"
class Segment: public Figure
{
      R2Point p,q;
    public: Segment(R2Point a, R2Point b)
       {
       p=a; q=b;
       };
    public: double area()
       {
       return 0.0;
       };
    public: double perimeter()
       {
       return 2.0*p.dist(p,q);
       };
    public: Figure *add(R2Point r)
        {
       if (p.isTriangle(p,q,r)) {
           Polygon *u; u=new Polygon(p,q,r); 
           return (u);
                                };
       if (q.inside(p,r)) q=r;
       if (p.inside(r,q)) p=r;
       return this;
       };
};
 
//Klass - " odnougolnik", realizuiushii interface figury
class Point: public Figure
{
      R2Point p;
    public: Point(R2Point q)
       {
       p=q;
       };
    public: double area()
       {
       return 0.0;
       };
    public: double perimeter()
       {
       return 0.0;
       };
    public: Figure *add(R2Point q)
            {
        if (!p.equal(p,q)) 
            {Segment *u; u=new Segment(p,q); return (u);}
        else return (this);
            };
};
 
//klass "nul-ugolnik", realizuiushiiinterface figury
class Void: public Figure
{
    public: double area()
       {
       return 0.0;
       };
    public: double perimeter()
       {
       return 0.0;
       };
    public: Figure *add(R2Point p)
       {
        Point *u;
        u = new Point(p);
        return (u);
       };
};
 
//Klass - "vypuklaia obolochka"
class Convex
{
    public: Figure *fig;
    public: Convex()
      {
        fig = new Void;
      };
    public: double area()
      {
      return fig->area();
            };
    public: double perimeter()
      {
      return fig->perimeter();
      };
    public: void add(R2Point p)
      {
      fig=fig->add(p);
      };
};
 
//Test dla vypukloi obolochki
int main(int argc, char* argv[])
{
    Convex convex;
       while (1)
        {
        double mx,my;
        cout<<"Vvedite koordinaty tochki"<<endl;
        cin>>mx; if (mx==-100) break;
        cin>>my; if (my==-100) break;
        R2Point m(mx,my);
        convex.add(m);
        cout<<"Perimeter= "<<convex.perimeter()<<endl;
        cout<<"Ploschad=  "<<convex.area()<<endl;
        };
    return 0;
}