Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define INF 1000010000
- #define nl '\n'
- #define pb push_back
- #define ppb pop_back
- #define mp make_pair
- #define fi first
- #define se second
- #define pii pair<int,int>
- #define pdd pair<double,double>
- #define all(c)(c).begin(),(c).end()
- #define SORT(c) sort(all(c))
- #define rep(i,n) for( int i = 0; i < n; ++i )
- #define repi(i,n) for( int i = 1 ; i <= n; ++i )
- #define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
- #define repf(j,i,n) for( int j = i ; j < n ; ++j )
- #define die(s){std::cout << s << nl;}
- #define dier(s){std::cout << s; return 0;}
- #define vi vector<int>
- typedef long long ll;
- #define EPS 1e-9
- using namespace std;
- struct pt{
- double x, y;
- };
- struct seg{
- pt p, q;
- int id;
- double get_y(double x) const{
- if(abs(p.x - q.x) < EPS) return p.y;
- return p.y +(q.y - p.y) *(x - p.x) /(q.x - p.x);
- }
- };
- inline bool intersect1d(double l1, double r1, double l2, double r2){
- if(l1 > r1) swap(l1, r1);
- if(l2 > r2) swap(l2, r2);
- return max(l1, l2) <= min(r1, r2) + EPS;
- }
- inline int vec(const pt & a, const pt & b, const pt & c){
- double s =(b.x - a.x) *(c.y - a.y) -(b.y - a.y) *(c.x - a.x);
- return abs(s)<EPS ? 0 : s>0 ? +1 : -1;
- }
- bool intersect(const seg & a, const seg & b){
- return intersect1d(a.p.x, a.q.x, b.p.x, b.q.x)
- && intersect1d(a.p.y, a.q.y, b.p.y, b.q.y)
- && vec(a.p, a.q, b.p) * vec(a.p, a.q, b.q) <= 0
- && vec(b.p, b.q, a.p) * vec(b.p, b.q, a.q) <= 0;
- }
- bool operator<(const seg & a, const seg & b){
- double x = max(min(a.p.x, a.q.x), min(b.p.x, b.q.x));
- return a.get_y(x) < b.get_y(x) - EPS;
- }
- struct event{
- double x;
- int tp, id;
- event(){ }
- event(double x, int tp, int id)
- : x(x), tp(tp), id(id)
- { }
- bool operator<(const event & e) const{
- if(abs(x - e.x) > EPS) return x < e.x;
- return tp > e.tp;
- }
- };
- set<seg> s;
- vector < set<seg>::iterator > where;
- inline set<seg>::iterator prev(set<seg>::iterator it){
- return it == s.begin() ? s.end() : --it;
- }
- inline set<seg>::iterator next(set<seg>::iterator it){
- return ++it;
- }
- int main(){
- vector<seg> a;
- int n = 0;
- int x1,y1,x2,y2;
- while(cin>> x1 >> y1 >> x2 >> y2){
- pt tp; tp.x = 0; tp.y = 0;
- seg sg; sg.p = tp; sg.q = tp;
- a.pb(sg);
- a[n].p.x = x1;
- a[n].p.y = y1;
- a[n].q.x = x2;
- a[n].q.y = y2;
- ++n;
- }
- vector<event> e;
- rep(i , n){
- e.pb(event(min(a[i].p.x, a[i].q.x), 1, i));
- e.pb(event(max(a[i].p.x, a[i].q.x), -1, i));
- }
- SORT(e);
- where.resize(a.size());
- rep(i , e.size()){
- int id = e[i].id;
- if(e[i].tp == 1){
- set<seg>::iterator
- nxt = s.lower_bound(a[id]),
- prv = prev(nxt);
- if(nxt != s.end() && intersect(*nxt, a[id]))
- dier("intersect");
- if(prv != s.end() && intersect(*prv, a[id]))
- dier("intersect");
- where[id] = s.insert(nxt, a[id]);
- }
- else{
- set<seg>::iterator
- nxt = next(where[id]),
- prv = prev(where[id]);
- if(nxt != s.end() && prv != s.end() && intersect(*nxt, *prv))
- dier("intersect");
- s.erase(where[id]);
- }
- }
- die("NOT intersect");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement