Advertisement
MystMe

Untitled

Dec 20th, 2017
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.07 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <set>
  4. #include <math.h>
  5.  
  6. using namespace std;
  7.  
  8. struct Point {
  9.     double x;
  10.     double y;
  11.  
  12.     Point() : x(0), y(0) {}
  13.     Point(double _x, double _y) : x(_x), y(_y) {}
  14. };
  15.  
  16. struct Arc;
  17. struct Segment;
  18.  
  19. struct Event {
  20.     double x;
  21.     Point point;
  22.     Arc *arc;
  23.     bool valid;
  24.  
  25.     Event(double _x, Point _point, Arc *_arc)
  26.             : x(_x), point(_point), arc(_arc), valid(true) {}
  27. };
  28. struct Arc {
  29.     Point point;
  30.     Arc *previous;
  31.     Arc *next;
  32.     Event *event;
  33.  
  34.     Segment *s0;
  35.     Segment *s1;
  36.  
  37.     explicit Arc(Point _point, Arc *_prev = nullptr, Arc *_next = nullptr)
  38.                     : point(_point), previous(_prev), next(_next), event(nullptr), s0(nullptr), s1(nullptr) {}
  39. };
  40.  
  41. vector<Segment*> output;
  42.  
  43. struct Segment {
  44.     Point start;
  45.     Point end;
  46.     bool done;
  47.  
  48.     explicit Segment(Point _start): start(_start), end(0,0), done(false) {
  49.         output.push_back(this);
  50.     }
  51.  
  52.     // Set the end point and mark as "done."
  53.     void finish(Point _end) {
  54.         if (done) {
  55.             return;
  56.         }
  57.         end = _end;
  58.         done = true;
  59.     }
  60. };
  61.  
  62. // "Greater than" comparison, for reverse sorting in priority queue.
  63. struct gt {
  64.     bool operator () (Point left, Point right) {
  65.         return left.x==right.x ? left.y>right.y : left.x>right.x;
  66.     }
  67.  
  68.     bool operator()(Event *left, Event *right) {
  69.         return left->x > right->x;
  70.     }
  71. };
  72.  
  73. Arc *root = nullptr;
  74. // Bounding box coordinates.
  75. double X0 = 0;
  76. double X1 = 0;
  77. double Y0 = 0;
  78. double Y1 = 0;
  79.  
  80. priority_queue<Point,  vector<Point>,  gt> points; // site events
  81. priority_queue<Event*, vector<Event*>, gt> events; // circle events
  82.  
  83. // Where do two parabolas intersect?
  84. Point intersection(Point first, Point second, double l)
  85. {
  86.     Point res;
  87.     Point tmp_point = first;
  88.  
  89.     double z0 = 2*(first.x - l);
  90.     double z1 = 2*(second.x - l);
  91.  
  92.     if (first.x == second.x)
  93.         res.y = (first.y + second.y) / 2;
  94.     else if (second.x == l)
  95.         res.y = second.y;
  96.     else if (first.x == l) {
  97.         res.y = first.y;
  98.         tmp_point = second;
  99.     } else {
  100.         // Use the quadratic formula.
  101.         double a = 1/z0 - 1/z1;
  102.         double b = -2*(first.y/z0 - second.y/z1);
  103.         double c = (first.y*first.y + first.x*first.x - l*l)/z0
  104.                    - (second.y*second.y + second.x*second.x - l*l)/z1;
  105.  
  106.         res.y = ( -b - sqrt(b*b - 4*a*c) ) / (2*a);
  107.     }
  108.     // Plug back into one of the parabola equations.
  109.     res.x = (tmp_point.x*tmp_point.x + (tmp_point.y-res.y)*(tmp_point.y-res.y) - l*l)/(2*tmp_point.x-2*l);
  110.     return res;
  111. }
  112.  
  113. // Will a new parabola at point p intersect with arc i?
  114. bool intersect(Point point, Arc *arc, Point *result)
  115. {
  116.     if (arc->point.x == point.x) return false;
  117.  
  118.     double a,b;
  119.     if (arc->previous) // Get the intersection of arc->prev, arc.
  120.         a = intersection(arc->previous->point, arc->point, point.x).y;
  121.     if (arc->next) // Get the intersection of arc->next, arc.
  122.         b = intersection(arc->point, arc->next->point, point.x).y;
  123.  
  124.     if ((!arc->previous || a <= point.y) && (!arc->next || point.y <= b)) {
  125.         result->y = point.y;
  126.  
  127.         result->x = (arc->point.x*arc->point.x + (arc->point.y-result->y)*(arc->point.y-result->y) - point.x*point.x)
  128.                     / (2*arc->point.x - 2*point.x);
  129.  
  130.         return true;
  131.     }
  132.     return false;
  133. }
  134.  
  135. // Find the rightmost point on the circle through a,b,c.
  136. bool circle(Point a, Point b, Point c, double *x, Point *o)
  137. {
  138.     // Check that bc is a "right turn" from ab.
  139.     if ((b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y) > 0)
  140.         return false;
  141.  
  142.     // Algorithm from O'Rourke 2ed p. 189.
  143.     double A = b.x - a.x,  B = b.y - a.y,
  144.             C = c.x - a.x,  D = c.y - a.y,
  145.             E = A*(a.x+b.x) + B*(a.y+b.y),
  146.             F = C*(a.x+c.x) + D*(a.y+c.y),
  147.             G = 2*(A*(c.y-b.y) - B*(c.x-b.x));
  148.  
  149.     if (G == 0) return false;  // Points are co-linear.
  150.  
  151.     // Point o is the center of the circle.
  152.     o->x = (D*E-B*F)/G;
  153.     o->y = (A*F-C*E)/G;
  154.  
  155.     // o.x plus radius equals max x coordinate.
  156.     *x = o->x + sqrt( pow(a.x - o->x, 2) + pow(a.y - o->y, 2) );
  157.     return true;
  158. }
  159.  
  160. // Look for a new circle event for arc i.
  161. void check_circle_event(Arc *i, double x0)
  162. {
  163.     // Invalidate any old event.
  164.     if (i->event && i->event->x != x0)
  165.         i->event->valid = false;
  166.     i->event = NULL;
  167.  
  168.     if (!i->previous || !i->next)
  169.         return;
  170.  
  171.     double x;
  172.     Point o;
  173.  
  174.     if (circle(i->previous->point, i->point, i->next->point, &x,&o) && x > x0) {
  175.         // Create new event.
  176.         i->event = new Event(x, o, i);
  177.         events.push(i->event);
  178.     }
  179. }
  180.  
  181. void front_insert(Point tmp_point)
  182. {
  183.     if (!root) {
  184.         root = new Arc(tmp_point);
  185.         return;
  186.     }
  187.  
  188.     for (Arc *arc = root; arc; arc = arc->next) {
  189.         Point z;
  190.         Point zz;
  191.         if (intersect(tmp_point,arc,&z)) {
  192.             // New parabola intersects arc arc.  If necessary, duplicate arc.
  193.             if (arc->next && !intersect(tmp_point,arc->next, &zz)) {
  194.                 arc->next->previous = new Arc(arc->point,arc,arc->next);
  195.                 arc->next = arc->next->previous;
  196.             }
  197.             else arc->next = new Arc(arc->point,arc);
  198.             arc->next->s1 = arc->s1;
  199.  
  200.             // Add tmp_point between arc and arc->next.
  201.             arc->next->previous = new Arc(tmp_point,arc,arc->next);
  202.             arc->next = arc->next->previous;
  203.  
  204.             arc = arc->next; // Now arc points to the new arc.
  205.  
  206.             // Add new half-edges connected to arc's endpoints.
  207.             arc->previous->s1 = arc->s0 = new Segment(z);
  208.             arc->next->s0 = arc->s1 = new Segment(z);
  209.  
  210.             // Check for new circle events around the new arc:
  211.             check_circle_event(arc, tmp_point.x);
  212.             check_circle_event(arc->previous, tmp_point.x);
  213.             check_circle_event(arc->next, tmp_point.x);
  214.  
  215.             return;
  216.         }
  217.     }
  218.  
  219.     // Special case: If tmp_point never intersects an arc, append it to the list.
  220.     Arc *i;
  221.     for (i = root; i->next; i=i->next) ; // Find the last node.
  222.  
  223.     i->next = new Arc(tmp_point,i);
  224.     // Insert segment between tmp_point and i
  225.     Point start;
  226.     start.x = X0;
  227.     start.y = (i->next->point.y + i->point.y) / 2;
  228.     i->s1 = i->next->s0 = new Segment(start);
  229. }
  230.  
  231. void process_point() {
  232.     Point tmp_point = points.top();
  233.     points.pop();
  234.     front_insert(tmp_point);
  235. }
  236.  
  237. void process_event()
  238. {
  239.     // Get the next event from the queue.
  240.     Event *e = events.top();
  241.     events.pop();
  242.  
  243.     if (e->valid) {
  244.         // Start a new edge.
  245.         Segment *s = new Segment(e->point);
  246.  
  247.         // Remove the associated arc from the front.
  248.         Arc *a = e->arc;
  249.         if (a->previous) {
  250.             a->previous->next = a->next;
  251.             a->previous->s1 = s;
  252.         }
  253.         if (a->next) {
  254.             a->next->previous = a->previous;
  255.             a->next->s0 = s;
  256.         }
  257.  
  258.         // Finish the edges before and after a.
  259.         if (a->s0) a->s0->finish(e->point);
  260.         if (a->s1) a->s1->finish(e->point);
  261.  
  262.         // Recheck circle events on either side of p:
  263.         if (a->previous) check_circle_event(a->previous, e->x);
  264.         if (a->next) check_circle_event(a->next, e->x);
  265.     }
  266.     delete e;
  267. }
  268.  
  269. void finish_edges()
  270. {
  271.     // Advance the sweep line so no parabolas can cross the bounding box.
  272.     double l = X1 + (X1-X0) + (Y1-Y0);
  273.  
  274.     // Extend each remaining segment to the new parabola intersections.
  275.     for (Arc *i = root; i->next; i = i->next)
  276.         if (i->s1)
  277.             i->s1->finish(intersection(i->point, i->next->point, l*2));
  278. }
  279.  
  280. void print_output()
  281. {
  282.     // Bounding box coordinates.
  283.     cout << X0 << " "<< X1 << " " << Y0 << " " << Y1 << endl;
  284.  
  285.     // Each output segment in four-column format.
  286.     vector<Segment*>::iterator i;
  287.     for (i = output.begin(); i != output.end(); i++) {
  288.         Point p0 = (*i)->start;
  289.         Point p1 = (*i)->end;
  290.         cout << p0.x << " " << p0.y << " " << p1.x << " " << p1.y << endl;
  291.     }
  292. }
  293.  
  294. int main()
  295. {
  296.     // Read points from input.
  297.     Point p;
  298.     while (cin >> p.x >> p.y) {
  299.         if(p.x == -100) {
  300.             break;
  301.         }
  302.  
  303.         points.push(p);
  304.  
  305.         // Keep track of bounding box size.
  306.         if (p.x < X0) X0 = p.x;
  307.         if (p.y < Y0) Y0 = p.y;
  308.         if (p.x > X1) X1 = p.x;
  309.         if (p.y > Y1) Y1 = p.y;
  310.     }
  311.     // Add 20% margins to the bounding box.
  312.     double dx = (X1-X0+1)/5.0; double dy = (Y1-Y0+1)/5.0;
  313.     X0 -= dx; X1 += dx; Y0 -= dy; Y1 += dy;
  314.  
  315.     // Process the queues; select the top element with smaller x coordinate.
  316.     while (!points.empty())
  317.         if (!events.empty() && events.top()->x <= points.top().x)
  318.             process_event();
  319.         else
  320.             process_point();
  321.  
  322.     // After all points are processed, do the remaining circle events.
  323.     while (!events.empty())
  324.         process_event();
  325.  
  326.     finish_edges(); // Clean up dangling edges.
  327.     print_output(); // Output the voronoi diagram.
  328. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement