smatskevich

Voronoj

Dec 20th, 2017
218
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <assert.h>
  4. #include <math.h>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <queue>
  8.  
  9. using std::vector;
  10. using std::priority_queue;
  11. using std::cin;
  12. using std::cout;
  13.  
  14. struct Point {
  15.     double X;
  16.     double Y;
  17.     int Pos;
  18.  
  19.     Point() : X( 0 ), Y( 0 ), Pos( -1 ) {}
  20.     bool operator==( const Point& other ) const { return X == other.X && Y == other.Y; }
  21. };
  22.  
  23. struct Vector {
  24.     double X;
  25.     double Y;
  26.  
  27.     Vector( const Point& p1, const Point& p2 ) : X( p2.X - p1.X ), Y( p2.Y - p1.Y ) {}
  28.     // Знак векторного произведения. Если больше 0, true, то поворот налево.
  29.     bool operator^( const Vector& other ) { return X * other.Y - Y * other.X > 0; }
  30. };
  31.  
  32. struct Event {
  33.     double Time;
  34.     bool IsNewPoint;
  35.     Point NewPoint;
  36.     int UpperRay;
  37.     int LowerRay;
  38.  
  39.     Event( const Point& point ) :
  40.         Time( point.X ), IsNewPoint( true ), NewPoint( point ), UpperRay( -1 ), LowerRay( -1 )
  41.     {
  42.     }
  43.     Event( double time, int upperRay, int lowerRay ) :
  44.         Time( time ), IsNewPoint( false ), UpperRay( upperRay ), LowerRay( lowerRay )
  45.     {
  46.     }
  47.     bool operator<( const Event& other ) const { return Time > other.Time; }
  48. };
  49.  
  50. // Луч, по которому движется пересечение парабол.
  51. struct Ray {
  52.     Point First; // С меньшей x-координатой.
  53.     Point Second; // С большей x-координатой.
  54.     bool IsUp; // true, если над второй точкой.
  55.     bool IsClosed; // Закрыт ли.
  56.  
  57.     Ray( const Point& first, const Point& second, bool isUp, bool isClosed = false ) :
  58.         First( first ), Second( second ), IsUp( isUp ), IsClosed( isClosed )
  59.     {
  60.     }
  61.     // Y-координата пересечения парабол в момент времени time.
  62.     double GetYAtTime( double time );
  63. };
  64.  
  65. // Линия - два луча. Если оба луча замкнуты, значит, получился отрезок.
  66. struct Line {
  67.     int Ray1;
  68.     int Ray2;
  69.  
  70.     Line( int ray1, int ray2 ) : Ray1( ray1 ), Ray2( ray2 ) {}
  71. };
  72.  
  73. // Дуга параболы.
  74. struct Arc {
  75.     Point Center;
  76.     int UpperRay; // Верхний луч. Индекс в массиве rais. -1, если нет.
  77.     int LowerRay; // Нижний луч. -1, если нет.
  78.  
  79.     Arc( const Point& point ) : Center( point ), UpperRay( -1 ), LowerRay( -1 ) {}
  80. };
  81.  
  82. // --------------------------------------------------------------------------------------------------------
  83.  
  84. double Ray::GetYAtTime( double time )
  85. {
  86.     assert( First.X != Second.X );
  87.     // Решаем систему уравнений:
  88.     // y^2 - 2Fy * y + 2(time - Fx) * x + Fx^2 + Fy^2 - time^2 = 0;
  89.     // x = (Sy - Fy)/(Fx - Sx) * y + (Fx^2 + Fy^2 - Sx^2 - Sy^2)/2(Fx - Sx)
  90.     double xCoef = 2.0 * ( time - First.X );
  91.     double b = -2.0 * First.Y + xCoef * ( Second.Y - First.Y ) / ( First.X - Second.X );
  92.     double c = First.X * First.X + First.Y * First.Y - time * time +
  93.         xCoef * ( First.X * First.X + First.Y * First.Y - Second.X * Second.X - Second.Y * Second.Y ) /
  94.         ( 2.0 * ( First.X - Second.X ) );
  95.     double d = b * b - 4 * c;
  96.     assert( d > 0 );
  97.     d = sqrt( d );
  98.     return IsUp ? ( -b + d ) / 2.0 : ( -b - d ) / 2.0;
  99. }
  100.  
  101. void ReadPoints( vector<Point>& points )
  102. {
  103.     while( true ) {
  104.         Point p;
  105.         cin >> p.X;
  106.         cin >> p.Y;
  107.         p.Pos = static_cast< int >( points.size() );
  108.         if( cin.eof() ) {
  109.             break;
  110.         }
  111.         points.push_back( p );
  112.     }
  113. }
  114.  
  115. // -----------------------------------------------------------------------
  116.  
  117. class CVoronoj {
  118. public:
  119.     CVoronoj( const vector<Point>& _points ) : points( _points ), lines( points.size(), vector<Line>() ) {}
  120.  
  121.     double Process();
  122.  
  123. private:
  124.     const vector<Point>& points;
  125.     priority_queue<Event> events;
  126.     vector<Arc> arcs;
  127.     vector<Ray> rais;
  128.     vector<vector<Line>> lines;
  129.  
  130.     void nextEvent();
  131.     void onNewPoint( double time, const Point& newPoint );
  132.     void onCross( double time, int upperRay, int lowerRay );
  133.     void checkCrossEvent( const Arc& arc );
  134.  
  135.     double calcAvgPolygonSize();
  136. };
  137.  
  138. double CVoronoj::Process()
  139. {
  140.     // Инициализируем массив событий.
  141.     for( int i = 0; i < static_cast< int >( points.size() ); ++i ) {
  142.         Event event( points[i] );
  143.         events.push( event );
  144.     }
  145.     // Обрабатываем события.
  146.     while( !events.empty() ) {
  147.         nextEvent();
  148.     }
  149.  
  150.     return calcAvgPolygonSize();
  151. }
  152.  
  153. void CVoronoj::nextEvent( )
  154. {
  155.     Event event = events.top( );
  156.     events.pop( );
  157.     if( arcs.empty( ) ) {
  158.         assert( event.IsNewPoint );
  159.         arcs.push_back( Arc( event.NewPoint ) );
  160.         return;
  161.     }
  162.     if( event.IsNewPoint ) {
  163.         onNewPoint( event.Time, event.NewPoint );
  164.     } else {
  165.         // Пересечение.
  166.         onCross( event.Time, event.UpperRay, event.LowerRay );
  167.     }
  168. }
  169.  
  170. void CVoronoj::onNewPoint( double time, const Point& newPoint )
  171. {
  172.     // Найдем дугу, на которую попадает точка.
  173.     int i = 0;
  174.     while( true ) {
  175.         assert( i < static_cast< int >( arcs.size() ) );
  176.         if( arcs[i].LowerRay == -1 ) {
  177.             break;
  178.         }
  179.         if( rais[arcs[i].LowerRay].GetYAtTime( time ) < newPoint.Y ) {
  180.             // Нашли дугу, содержащую точку.
  181.             break;
  182.         }
  183.         ++i;
  184.     }
  185.     // Добавим два луча одной прямой. И саму прямую.
  186.     Ray upperRay( arcs[i].Center, newPoint, true );
  187.     Ray lowerRay( arcs[i].Center, newPoint, false );
  188.     rais.push_back( upperRay );
  189.     rais.push_back( lowerRay );
  190.     Line line( rais.size() - 2, rais.size() - 1 );
  191.     lines[arcs[i].Center.Pos].push_back( line );
  192.     lines[newPoint.Pos].push_back( line );
  193.  
  194.     // Разделим дугу arcs[i] на три.
  195.     Arc upper( arcs[i].Center );
  196.     Arc middle( newPoint );
  197.     Arc lower( arcs[i].Center );
  198.     upper.UpperRay = arcs[i].UpperRay;
  199.     upper.LowerRay = rais.size() - 2;
  200.     middle.UpperRay = upper.LowerRay;
  201.     middle.LowerRay = rais.size() - 1;
  202.     lower.UpperRay = middle.LowerRay;
  203.     lower.LowerRay = arcs[i].LowerRay;
  204.  
  205.     // У верхней и нижней дуги могут появиться пересечения.
  206.     checkCrossEvent( upper );
  207.     checkCrossEvent( lower );
  208.  
  209.     // Подменим дугу arcs[i] на три в массиве дуг.
  210.     arcs[i] = upper;
  211.     arcs.insert( arcs.begin() + i + 1, 2, middle );
  212.     arcs[i + 2] = lower;
  213. }
  214.  
  215. void CVoronoj::onCross( double time, int upperRay, int lowerRay )
  216. {
  217.     assert( upperRay != -1 );
  218.     assert( lowerRay != -1 );
  219.     // Пересечение могло запоздать.
  220.     if( rais[upperRay].IsClosed || rais[lowerRay].IsClosed ) {
  221.         return;
  222.     }
  223.     // Найдем дугу, которая схлопнулась.
  224.     int i = 0;
  225.     for( ; i < static_cast< int >( arcs.size() ); ++i ) {
  226.         if( arcs[i].UpperRay == upperRay ) {
  227.             break;
  228.         }
  229.     }
  230.     // Это не может быть первая или последняя дуга.
  231.     assert( i > 0 );
  232.     assert( i < static_cast< int >( arcs.size() - 1 ) );
  233.     assert( arcs[i].LowerRay == lowerRay );
  234.  
  235.     // Завершим лучи.
  236.     rais[upperRay].IsClosed = true;
  237.     rais[lowerRay].IsClosed = true;
  238.  
  239.     // Добавим новые лучи.
  240.     Point middleCenter = arcs[i].Center;
  241.     Point upperCenter = rais[upperRay].First == middleCenter ? rais[upperRay].Second : rais[upperRay].First;
  242.     Point lowerCenter = rais[lowerRay].First == middleCenter ? rais[lowerRay].Second : rais[lowerRay].First;
  243.     if( upperCenter.X < lowerCenter.X ) {
  244.         rais.push_back( Ray( upperCenter, lowerCenter, !rais[lowerRay].IsUp, true ) );
  245.         rais.push_back( Ray( upperCenter, lowerCenter, rais[lowerRay].IsUp ) );
  246.     } else {
  247.         rais.push_back( Ray( lowerCenter, upperCenter, !rais[upperRay].IsUp, true ) );
  248.         rais.push_back( Ray( lowerCenter, upperCenter, rais[upperRay].IsUp ) );
  249.     }
  250.     // Добавим прямые.
  251.     Line line( rais.size() - 2, rais.size() - 1 );
  252.     lines[upperCenter.Pos].push_back( line );
  253.     lines[lowerCenter.Pos].push_back( line );
  254.  
  255.     // Обновим дугу сверху и снизу.
  256.     arcs[i - 1].LowerRay = static_cast< int >( rais.size() ) - 1;
  257.     arcs[i + 1].UpperRay = static_cast< int >( rais.size() ) - 1;
  258.     // Удалим дугу.
  259.     arcs.erase( arcs.begin() + i );
  260.     checkCrossEvent( arcs[i - 1] );
  261.     checkCrossEvent( arcs[i] );
  262. }
  263.  
  264. void CVoronoj::checkCrossEvent( const Arc& arc )
  265. {
  266.     if( arc.UpperRay == -1 || arc.LowerRay == -1 ) {
  267.         return;
  268.     }
  269.     const Ray& upperRay = rais[arc.UpperRay];
  270.     const Ray& lowerRay = rais[arc.LowerRay];
  271.     Point p2 = arc.Center;
  272.     Point p1 = upperRay.First == p2 ? upperRay.Second : upperRay.First;
  273.     Point p3 = lowerRay.First == p2 ? lowerRay.Second : lowerRay.First;
  274.  
  275.     // Если точки p1, p2, p3 образуют левый поворот, то пересечение есть.
  276.     if( Vector( p1, p2 ) ^ Vector( p2, p3 ) ) {
  277.         // Найдем время, при котором произойдет пересечение.
  278.         // x = (p2y - p1y)/(p1x - p2x) y + (p1x^2 + p1y^2 - p2x^2 - p2y^2)/2*(p1x - p2x).
  279.         double a1 = ( p2.Y - p1.Y ) / ( p1.X - p2.X );
  280.         double a2 = ( p3.Y - p2.Y ) / ( p2.X - p3.X );
  281.         double b1 = ( p1.X * p1.X + p1.Y * p1.Y - p2.X * p2.X - p2.Y * p2.Y ) / ( 2.0 * ( p1.X - p2.X ) );
  282.         double b2 = ( p2.X * p2.X + p2.Y * p2.Y - p3.X * p3.X - p3.Y * p3.Y ) / ( 2.0 * ( p2.X - p3.X ) );
  283.         double y = ( b2 - b1 ) / ( a1 - a2 );
  284.         double x = a1 * y + b1;
  285.         double dist = sqrt( ( p1.X - x ) * ( p1.X - x ) + ( p1.Y - y ) * ( p1.Y - y ) );
  286.         double time = x + dist;
  287.  
  288.         Event event( time, arc.UpperRay, arc.LowerRay );
  289.         events.push( event );
  290.     }
  291. }
  292.  
  293. int main()
  294. {
  295.     vector<Point> points;
  296.     ReadPoints( points );
  297.     CVoronoj voronoj( points );
  298.     cout << voronoj.Process();
  299.     return 0;
  300. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×