Advertisement
Guest User

intersecție segmente

a guest
Jul 26th, 2017
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.40 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <typeinfo>
  3. #define NMAX 100001
  4. #define x second
  5. #define y first
  6. using namespace std;
  7. ifstream fin("is.in");
  8. ofstream fout("is.out");
  9. typedef pair<int, int>point;
  10. struct event
  11. {
  12.     point p1,p2;
  13.     int type;
  14.     event() {};
  15.     event(point p1,point p2, int type) : p1(p1), p2(p2),type(type) {};
  16. };
  17. int n,e, nrint;
  18. event events[NMAX];
  19. bool compare(event a, event b)
  20. {
  21.     return a.p1.x<b.p1.x;
  22. }
  23. set<point>s;
  24. void hv_intersection()
  25. {
  26.     for (int i=0;i<e;++i)
  27.     {
  28.             event c = events[i];
  29.             if (c.type==0)
  30.                 s.insert(c.p1);
  31.             else if (c.type==1)
  32.                 s.erase(c.p2);
  33.             else
  34.             {
  35.                 for (typeof(s.begin()) it=s.lower_bound(make_pair(c.p1.y,-1));it!=s.end() && it->y<=c.p2.y; it++)
  36.                                 nrint++;
  37.             }
  38.         }
  39. }
  40. int main()
  41. {
  42.     int i;
  43.     fin>>n;
  44.     int p1x,p1y,p2x,p2y;
  45.     for(i=0;i<n;i++)
  46.     {
  47.         fin>>p1x>>p1y>>p2x>>p2y;
  48.         if(p1x==p2x)
  49.         {
  50.             events[e++]=event(make_pair(p1y,p1x),make_pair(p2y,p2x),2);
  51.         }
  52.         else
  53.         {
  54.             events[e++]=event(make_pair(p1y,p1x),make_pair(p2y,p2x),0);
  55.             events[e++]=event(make_pair(p2y,p2x),make_pair(p1y,p1x),1);
  56.         }
  57.     }
  58.     sort(events, events+e,compare);
  59.     hv_intersection();
  60.     fout<<nrint;
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement