Advertisement
osipyonok

1505

May 30th, 2016
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.06 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. #define INF 1000010000
  4. #define nl '\n'
  5. #define pb push_back
  6. #define ppb pop_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define pii pair<int,int>
  11. #define pdd pair<double,double>
  12. #define all(c)(c).begin(),(c).end()
  13. #define SORT(c) sort(all(c))
  14. #define rep(i,n) for( int i = 0; i < n; ++i )
  15. #define repi(i,n) for( int i = 1 ; i <= n; ++i )
  16. #define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
  17. #define repf(j,i,n) for( int j = i ; j < n ; ++j )
  18. #define die(s){std::cout << s << nl;}
  19. #define dier(s){std::cout << s; return 0;}
  20. #define vi vector<int>
  21. typedef long long ll;
  22. #define EPS 1e-9
  23.  
  24. using namespace std;
  25.  
  26.  
  27. struct pt{
  28.     double x, y;
  29. };
  30.  
  31. struct seg{
  32.     pt p, q;
  33.     int id;
  34.  
  35.     double get_y(double x) const{
  36.         if(abs(p.x - q.x) < EPS)  return p.y;
  37.         return p.y +(q.y - p.y) *(x - p.x) /(q.x - p.x);
  38.     }
  39. };
  40.  
  41.  
  42. inline bool intersect1d(double l1, double r1, double l2, double r2){
  43.     if(l1 > r1)  swap(l1, r1);
  44.     if(l2 > r2)  swap(l2, r2);
  45.     return max(l1, l2) <= min(r1, r2) + EPS;
  46. }
  47.  
  48. inline int vec(const pt & a, const pt & b, const pt & c){
  49.     double s =(b.x - a.x) *(c.y - a.y) -(b.y - a.y) *(c.x - a.x);
  50.     return abs(s)<EPS ? 0 : s>0 ? +1 : -1;
  51. }
  52.  
  53. bool intersect(const seg & a, const seg & b){
  54.     return intersect1d(a.p.x, a.q.x, b.p.x, b.q.x)
  55.         && intersect1d(a.p.y, a.q.y, b.p.y, b.q.y)
  56.         && vec(a.p, a.q, b.p) * vec(a.p, a.q, b.q) <= 0
  57.         && vec(b.p, b.q, a.p) * vec(b.p, b.q, a.q) <= 0;
  58. }
  59.  
  60.  
  61. bool operator<(const seg & a, const seg & b){
  62.     double x = max(min(a.p.x, a.q.x), min(b.p.x, b.q.x));
  63.     return a.get_y(x) < b.get_y(x) - EPS;
  64. }
  65.  
  66.  
  67. struct event{
  68.     double x;
  69.     int tp, id;
  70.  
  71.     event(){ }
  72.     event(double x, int tp, int id)
  73.         : x(x), tp(tp), id(id)
  74.     { }
  75.  
  76.     bool operator<(const event & e) const{
  77.         if(abs(x - e.x) > EPS)  return x < e.x;
  78.         return tp > e.tp;
  79.     }
  80. };
  81.  
  82. set<seg> s;
  83. vector < set<seg>::iterator > where;
  84.  
  85. inline set<seg>::iterator prev(set<seg>::iterator it){
  86.     return it == s.begin() ? s.end() : --it;
  87. }
  88.  
  89. inline set<seg>::iterator next(set<seg>::iterator it){
  90.     return ++it;
  91. }
  92.  
  93. int main(){
  94.     vector<seg> a;
  95.     int n = 0;
  96.     int x1,y1,x2,y2;
  97.     while(cin>> x1 >> y1 >> x2 >> y2){
  98.         pt tp; tp.x = 0; tp.y = 0;
  99.         seg sg; sg.p = tp; sg.q = tp;
  100.         a.pb(sg);
  101.         a[n].p.x = x1;
  102.         a[n].p.y = y1;
  103.         a[n].q.x = x2;
  104.         a[n].q.y = y2;
  105.         ++n;
  106.     }
  107.    
  108.     vector<event> e;
  109.    
  110.     rep(i , n){
  111.         e.pb(event(min(a[i].p.x, a[i].q.x),  1, i));
  112.         e.pb(event(max(a[i].p.x, a[i].q.x), -1, i));
  113.     }
  114.     SORT(e);
  115.     where.resize(a.size());
  116.     rep(i , e.size()){
  117.         int id = e[i].id;
  118.         if(e[i].tp == 1){
  119.             set<seg>::iterator
  120.                 nxt = s.lower_bound(a[id]),
  121.                 prv = prev(nxt);
  122.             if(nxt != s.end() && intersect(*nxt, a[id]))
  123.                 dier("intersect");
  124.             if(prv != s.end() && intersect(*prv, a[id]))
  125.                 dier("intersect");
  126.             where[id] = s.insert(nxt, a[id]);
  127.         }
  128.         else{
  129.             set<seg>::iterator
  130.                 nxt = next(where[id]),
  131.                 prv = prev(where[id]);
  132.             if(nxt != s.end() && prv != s.end() && intersect(*nxt, *prv))
  133.                 dier("intersect");
  134.             s.erase(where[id]);
  135.         }
  136.     }
  137.     die("NOT intersect");
  138.     return 0;
  139. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement