API tools faq
paste
Advertisement
kpfp_linux

Untitled

kpfp_linux
Nov 12th, 2012
62
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.58 KB | None | 0 0
raw download clone embed print report
  1. #include <cstdio>
  2. #include <cassert>
  3. #include <algorithm>
  4. #include <functional>
  5. #include <iostream>
  6. #include <limits>
  7. #include <queue>
  8. #include <set>
  9. #include <string>
  10. #include <tuple>
  11. #include <vector>
  12.  
  13. using namespace std;
  14.  
  15. template <typename T> int sgn(T val) {
  16.     return (T(0) < val) - (val < T(0));
  17. }
  18.  
  19. const double EPS = 0.0001;
  20. inline bool eq(double d1, double d2) {
  21.   const double d = d1-d2;
  22.   return d > (-EPS) && d < EPS;
  23. }
  24. inline bool le(double d1, double d2) {
  25.   return d1-d2 < -EPS;
  26. }
  27. inline bool ge(double d1, double d2) {
  28.   return d1-d2 > EPS;
  29. }
  30.  
  31. struct Pt {
  32.   double x, y;
  33.   Pt(double _x, double _y) : x(_x), y(_y) {}
  34.   Pt(const Pt &rr) : x(rr.x), y(rr.y) {}
  35.   bool operator<(const Pt& rr) const {
  36.     return make_pair(x, y) < make_pair(rr.x, rr.y);
  37.   }
  38.   bool operator>(const Pt& rr) const {
  39.     return make_pair(x, y) > make_pair(rr.x, rr.y);
  40.   }
  41.   friend bool operator==(const Pt &a, const Pt &b);
  42.   friend ostream& operator<<(ostream &stream, const Pt &p);
  43. };
  44. bool operator==(const Pt &a, const Pt &b) {
  45.   return !(a<b || a>b);
  46. }
  47. ostream& operator<<(ostream &stream, const Pt &p) {
  48.   stream << "(" << p.x << "," << p.y << ")";
  49.   return stream;
  50. }
  51.  
  52.  
  53.  
  54. enum Side {
  55.   ONLEFT  = 0, // explicit for a reason -- don't change!
  56.   ONLINE  = 1,
  57.   ONRIGHT = 3
  58. };
  59. inline double det(double px, double py, double qx, double qy, double rx, double ry) {
  60.   return (px-rx)*(qy-ry)-(qx-rx)*(py-ry);
  61. }
  62. inline double det(const Pt &p, const Pt &q, const Pt &r) {
  63.   return det(p.x, p.y, q.x, q.y, r.x, r.y);
  64. }
  65. inline Side whichSide(const Pt &a, const Pt &b, const Pt &c) {
  66.   const double d = det(a,b,c);
  67.   if(le(d,0.0))
  68.     return ONRIGHT;
  69.   if(ge(d,0.0))
  70.     return ONLEFT;
  71.   return ONLINE;
  72. }
  73.  
  74. struct Seg {
  75.   Pt a, b;
  76.   char name;
  77.  
  78.   Seg(const Pt _a, const Pt _b, const char _name = '_') : a(_a), b(_b), name(_name) {}
  79.  
  80.   bool contains(const Pt& rr) const {
  81.     if(whichSide(a,b,rr) != ONLINE)
  82.       return false;
  83.     return ( min(a.x,b.x) <= rr.x && rr.x <= max(a.x,b.x)
  84.         &&   min(a.y,b.y) <= rr.y && rr.y <= max(a.y,b.y) );
  85.   }
  86.   bool operator^(const Seg& rr) const { // przecięcie
  87.     const Pt& p1 = a;
  88.     const Pt& p2 = b;
  89.     const Pt& p3 = rr.a;
  90.     const Pt& p4 = rr.b;
  91.     Side d1 = whichSide(p3, p4, p1);
  92.     Side d2 = whichSide(p3, p4, p2);
  93.     Side d3 = whichSide(p1, p2, p3);
  94.     Side d4 = whichSide(p1, p2, p4);
  95.     if(d1+d2 == ONLEFT+ONRIGHT
  96.         && d3+d4 == ONLEFT+ONRIGHT)     return true;
  97.     if(d1 == ONLINE && rr.contains(p1)) return true;
  98.     if(d2 == ONLINE && rr.contains(p2)) return true;
  99.     if(d3 == ONLINE && contains(p3))    return true;
  100.     if(d4 == ONLINE && contains(p4))    return true;
  101.     return false;
  102.   }
  103.   Pt getIntersection(const Seg& rr) const {
  104.     assert(operator^(rr));
  105.     const double &x1 = a.x;
  106.     const double &x2 = b.x;
  107.     const double &x3 = rr.a.x;
  108.     const double &x4 = rr.b.x;
  109.     const double &y1 = a.y;
  110.     const double &y2 = b.y;
  111.     const double &y3 = rr.a.y;
  112.     const double &y4 = rr.b.y;
  113.     const double dvsr = (x1-x2)*(y3-y4)-(x3-x4)*(y1-y2);
  114.     const double x    = ( x2*(x3*y4-x4*y3+(x4-x3)*y1)+x1*(x4*y3-x3*y4+(x3-x4)*y2) )  / dvsr;
  115.     const double y    = ( y2*(x3*y4-x4*y3)+y1*(x4*y3-x3*y4)+x2*y1*(y4-y3)+x1*y2*(y3-y4) ) / dvsr;
  116.     return Pt(x,y);
  117.   }
  118.   bool operator<(const Seg &rr) const {
  119.     if(whichSide(a, b, rr.a) == ONLINE)
  120.       return whichSide(a,b, rr.b) == ONRIGHT;
  121.     return whichSide(a, b, rr.a) == ONRIGHT;
  122.   }
  123.   bool operator>(const Seg &rr) const {
  124.     if(whichSide(a, b, rr.a) == ONLINE)
  125.       return whichSide(a,b, rr.b) == ONLEFT;
  126.     return whichSide(a, b, rr.a) == ONLEFT;
  127.   }
  128.   bool operator==(const Seg &rr) const {
  129.     return make_pair(a, b) == make_pair(rr.a, rr.b);
  130.   }
  131.   friend ostream& operator<<(ostream &stream, const Seg &p);
  132. };
  133. ostream& operator<<(ostream &stream, const Seg &l) {
  134.   stream << "[" << l.name << ": " << l.a << " --> " << l.b << "]";
  135.   return stream;
  136. }
  137.  
  138. struct Event {
  139.   enum Event_t { Begin, Intersection, Vertical, End } evt;
  140.   Pt p;
  141.   Seg l1, l2;
  142.   Event(Event_t _evt, const Pt &_p, const Seg &_l1) : evt(_evt), p(_p), l1(_l1), l2(_l1) {}
  143.   Event(Event_t _evt, const Pt &_p, const Seg &_l1, const Seg &_l2) : evt(_evt), p(_p), l1(_l1), l2(_l2) {}
  144.   bool operator<(const Event &rr) const {
  145.     if(make_pair(p.x,evt) == make_pair(rr.p.x, rr.evt))
  146.       return make_pair(p.y, l1) < make_pair(rr.p.y, rr.l1);
  147.     return make_pair(p.x,evt) < make_pair(rr.p.x, rr.evt);
  148.   }
  149.   bool operator>(const Event &rr) const {
  150.     if(make_pair(p.x,evt) == make_pair(rr.p.x, rr.evt))
  151.       return make_pair(p.y, l1) > make_pair(rr.p.y, rr.l1);
  152.     return make_pair(p.x,evt) > make_pair(rr.p.x, rr.evt);
  153.   }
  154.   bool operator==(const Event &rr) const {
  155.     return make_pair(p.x,evt) == make_pair(rr.p.x, rr.evt) && make_pair(p.y, l1) < make_pair(rr.p.y, rr.l1);
  156.   }
  157.   friend ostream& operator<<(ostream &stream, const Event &e);
  158. };
  159. ostream& operator<<(ostream &stream, const Event &e) {
  160.   switch(e.evt) {
  161.     case Event::Begin:
  162.       stream << "{beg " << e.p << ": " << e.l1 << " }";
  163.       break;
  164.     case Event::End:
  165.       stream << "{end " << e.p << ": " << e.l1 << " }";
  166.       break;
  167.     case Event::Intersection:
  168.       stream << "{int " << e.p << ": " << e.l1 << " x " << e.l2 << " }";
  169.       break;
  170.     case Event::Vertical:
  171.     default:
  172.       stream << "{vrt " << e.p << ": " << e.l1 << " }";
  173.   }
  174.   return stream;
  175. }
  176.  
  177. struct segcmp {
  178.   bool operator()(const Seg &p, const Seg &q) const {
  179.     bool less = p > q;
  180.     cout << "                " << p << (less ? "  < " : " >= ") << q << "\n";
  181.     return less;
  182.   }
  183. };
  184.  
  185. typedef set<Seg, segcmp> tree;
  186. typedef set<Seg, segcmp>::iterator tree_iterator;
  187. typedef priority_queue<const Event, vector<Event>, greater<Event> > pqueue; // TODO usunąć drugi argument templatki
  188.  
  189. void printset(const char* msg, const tree &t) {
  190.   cout << "    " << msg << "SL→ ";
  191.   for(tree_iterator it = t.begin(); it!=t.end(); ++it)
  192.     cout << *it << " , ";
  193.   cout << "\n";
  194. }
  195.  
  196. int main() {
  197.   assert( det(0,0,0,1,1,1) < 0);
  198.   assert( det(0,0,0,1,-1,1) > 0);
  199.   assert( (Seg(Pt(0,0),Pt(0,1)) ^ Seg(Pt(0,0),Pt(1,0))) == true);
  200.   assert( (Seg(Pt(0,0),Pt(0,3)) ^ Seg(Pt(-1,1),Pt(1,1))) == true);
  201.   assert( (Seg(Pt(0,0),Pt(4,4))).contains(Pt(2,2)) );
  202.   assert( (Seg(Pt(0,0),Pt(4,4))).getIntersection(Seg(Pt(4,4),Pt(0,0))) == Pt(2,2) );
  203.   assert( (Seg(Pt(3,7),Pt(7,7)) ^ Seg(Pt(7,7),Pt(8,7))) == true );
  204.   assert( make_pair(5,1) > make_pair(3,7) );
  205.  
  206.   int N;
  207.   pqueue ksi;
  208.  
  209.   scanf(" %d ", &N);
  210.   for(int i=0; i<N; ++i) {
  211.     char n;
  212.     double ax, ay, bx, by;
  213.     scanf(" %c %lf %lf %lf %lf ", &n, &ax, &ay, &bx, &by);
  214.  
  215.     Pt a(ax,ay);
  216.     Pt b(bx,by);
  217.     if(eq(ax, bx)) {
  218.       if(a < b)
  219.         ksi.push(Event(Event::Vertical, a, Seg(a,b,n)));
  220.       else
  221.         ksi.push(Event(Event::Vertical, b, Seg(a,b,n)));
  222.     } else {
  223.       if(a < b) {
  224.         ksi.push(Event(Event::Begin, a, Seg(a,b,n)));
  225.         ksi.push(Event(Event::End, b, Seg(a,b,n)));
  226.       } else {
  227.         ksi.push(Event(Event::Begin, b, Seg(b,a,n)));
  228.         ksi.push(Event(Event::End, a, Seg(b,a,n)));
  229.       }
  230.     }
  231.   }
  232.  
  233.   tree SL;
  234.   unsigned int tmp_size = 0;
  235.   while(! ksi.empty()) {
  236.     Event evt = ksi.top(); ksi.pop();
  237.     cout << evt << "\n";
  238.  
  239.     pair<tree_iterator,bool> ins;
  240.     tree_iterator pred, succ, it;
  241.     const Seg &seg = evt.l1;
  242.  
  243.     printset("pre:  ", SL);
  244.  
  245.     switch(evt.evt) {
  246.       case Event::Begin:
  247.         assert(SL.size() == tmp_size);
  248.         ins = SL.insert(seg);
  249.         pred = ins.first;
  250.         succ = ins.first;
  251.         assert(SL.size() == ++tmp_size);
  252.         if((pred != SL.begin()) && (seg ^ (*(--pred)))) { // TODO: while ma być!
  253.           ksi.push(Event(Event::Intersection, seg.getIntersection(*pred), *pred, seg));
  254.           cout << "    pusz intersection (1): " <<  *pred << " x " << seg << "\n";
  255.           assert(!(seg == *pred));
  256.         }
  257.         if((++succ != SL.end())   && (seg ^ (*succ))) { // TODO: while ma być!
  258.           ksi.push(Event(Event::Intersection, seg.getIntersection(*succ), seg, *succ));
  259.           cout << "    pusz intersection (1): " <<  seg << " x " << *succ << "\n";
  260.           assert(!(seg == *succ));
  261.         }
  262.         assert(SL.size() == tmp_size);
  263.         break;
  264.  
  265.       case Event::End:
  266.         assert(SL.size() == tmp_size);
  267.         it = SL.find(seg);
  268.         assert(it != SL.end());
  269.         pred = it;
  270.         succ = it;
  271.        
  272.         if(pred != SL.begin() && succ != SL.end() && (*--pred)^(*++succ)) {
  273.           const Pt I = (*pred).getIntersection(*succ);
  274.           // tu sprawdzenie, czy I należy juz do ksi
  275.           cout << "    pusz intersection (2): " <<  *pred << " x " << *succ << "\n";
  276.           ksi.push(Event(Event::Intersection, I, (*pred), (*succ)));
  277.           assert(!(*pred == *succ));
  278.         }
  279.         tmp_size = SL.size();
  280.         SL.erase(it);
  281.         assert(SL.size() == --tmp_size);
  282.         break;
  283.  
  284.       case Event::Vertical:
  285.         // TODO: to be done
  286.         break;
  287.  
  288.       case Event::Intersection:
  289.         assert(SL.size() == tmp_size);
  290.         Seg sA = evt.l1;
  291.         Seg sB = evt.l2;
  292.         cout << "\t\t\tUsuwam: " << sA << " oraz " << sB << "\n";
  293.         assert( SL.find(sA) != SL.end() );
  294.         assert( SL.find(sB) != SL.end() );
  295.         SL.erase(SL.find(sA));
  296.         SL.erase(SL.find(sB));
  297.         printset("inter (1): ", SL);
  298.         assert(tmp_size -2 == SL.size());
  299.         sA.a = sB.a = evt.p;
  300.         if(sB < sA)
  301.           swap(sA, sB);
  302.         cout << "\t\t\tPoprawione p, wstawiam: " << sA << " < " << sB << "\n";
  303.         pred = SL.insert(sA).first;
  304.         succ = SL.insert(sB).first;
  305.         printset("inter (2): ", SL);
  306.         assert( SL.find(sA) != SL.end() );
  307.         assert( SL.find(sB) != SL.end() );
  308.         assert( ((sA > sB) && (!((sB > sA)))) || ((sB > sA) && (!((sA > sB)))) );
  309.         cout << "\t\t\tSize " << SL.size() << " =?= " << tmp_size << "\n";
  310.         assert(SL.size() == tmp_size);
  311.         if(pred != SL.begin() && sA ^ *--pred && !(sB == *pred)) {
  312.           assert(!(sA == *pred));
  313.           assert(!(sB == *pred));
  314.           ksi.push(Event(Event::Intersection, sA.getIntersection(*pred), *pred, sA));
  315.           cout << "    pusz intersection (3a): " <<  *pred << " x " << sA << "\n";
  316.         }
  317.         if(++succ != SL.end() && sB ^ *succ && !(sA == *succ)) {
  318.           assert(!(sA == *succ));
  319.           assert(!(sB == *succ));
  320.           ksi.push(Event(Event::Intersection, sB.getIntersection(*succ), *succ, sB));
  321.           cout << "    pusz intersection (3b): " <<  *succ << " x " << sB << "\n";
  322.         }
  323.     }
  324.  
  325.     printset("post: ", SL);
  326.   }
  327.  
  328.   return 0;
  329. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!