11343 - Isolated Segments

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

Re: 11343 - Isolated Segments

Post by Farsan » Tue Mar 03, 2015 12:54 pm

I am getting RTE on this problem.I tried to implement bentley ottmann algorithm.I know this problem can be solved in O(n^2) but i wanted to check correctness of my implemented bentley ottmann.Can anyone provide me some test cases?

Code: Select all

#include <bits/stdc++.h>
#define EPS 1e-9
using namespace std;

struct point
{
    double x,y;
    point()
    {
        x=0;
        y=0;
    }
};

struct line//line is represented in form ax+by+c=0
{
    double a,b,c;
    line()
    {
        a=0;
        b=0;
        c=0;
    }
};

line point_to_line(point p1,point p2)
{
    //always in the form ax+by+c=0
    line l;
    //not in canonical form.a,b,c, is double
    if(p1.x==p2.x)
    {
        l.a=1.0;
        l.b=0.0;
        l.c=-p1.x;
    }
    else
    {
        l.a=-(double)(p1.y-p2.y)/(p1.x-p2.x);
        l.b=1.0;
        l.c=-(double)(l.a*p1.x)-(l.b*p1.y);
    }
    return l;
}


// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(point p, point q, point r)
{
    // See 10th slides from following link for derivation of the formula
    // http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;  // colinear

    return (val > 0)? 1: 2; // clock or counterclock wise
}


// point q lies on line segment 'pr'
bool onSegment(point p, point q, point r)
{
    if(orientation(p,q,r)!=0)//not colinear
        return false;
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
        q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
       return true;

    return false;
}
//returns true if line segment 'p1q1' and 'p2q2' intersect.
bool doIntersect(point p1, point q1, point p2, point q2)
{
    // Find the four orientations needed for general and
    // special cases
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);
    // General case
    if (o1 != o2 && o3 != o4)
        return true;

    // Special Cases
    // p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;

    // p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;

    // p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;

     // p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false; // Doesn't fall in any of the above cases
}

bool areparallel(line l1,line l2)
{
    return (fabs(l1.a-l2.a)<EPS && fabs(l1.b-l2.b)<EPS);
}

bool aresame(line l1,line l2)
{
    return (areparallel(l1,l2)&&(fabs(l1.c-l2.c)<EPS));
}

bool does_intersect(line l1,line l2,point *p)
{
    if(aresame(l1,l2))
        return false;
    if(areparallel(l1,l2))
        return false;
    p->x=(l2.b*l1.c-l1.b*l2.c)/(l2.a*l1.b-l1.a*l2.b);
    if(fabs(l1.b>EPS))//special case for vertical line to avoid division by zero
    {
        p->y=-(l1.a*p->x+l1.c)/l1.b;
    }
    else
    {
        p->y=-(l2.a*p->x+l2.c)/l2.b;
    }
    return true;
}

struct line_segment
{
    double y;
    int line_id;
    line_segment()
    {
        y=0;
        line_id=0;
    }
    //bool operator<(const record& rhs, const record& next)
};

bool operator<(const line_segment& l1,const line_segment& l2)
{
    if(fabs(l1.y-l2.y)<EPS)
    return l1.line_id<l2.line_id;//multiple line can start at same point
    return l1.y>l2.y;
}

struct event_point
{
    int label;//start(1)/intersection(2)/end(3)
    int corresponding_line;//relevant if point is start point or end point
    int line1,line2;//relevant with intersection point
    double x,y;
    event_point()
    {
        x=0;
        y=0;
        corresponding_line=0;
        line1=0;
        line2=0;
    }
};

bool operator<(const event_point& ev1,const event_point& ev2)
{
    if(fabs(ev1.x-ev2.x)<EPS)
    {
            if(ev1.label==ev2.label)
            {
                //will process nodes from top to bottom
                return ev1.y<ev2.y;
            }
             //if have same x coordinate want to sort according to start point(1),intersection point(2),end point (3)
            return ev1.label>ev2.label;
    }
    else
    return ev1.x>ev2.x;//lowest x value comes first.
}

set<line_segment>::iterator lsit[700];

struct ans
{
    int line1,line2;
    point intersecting_point;
    ans()
    {
        line1=0;
        line2=0;
        intersecting_point.x=0;
        intersecting_point.y=0;
    }
};

bool operator<(const ans& p,const ans& q)
{
    if(p.line1==q.line1)
        return p.line2<q.line2;
    return p.line1<q.line1;
}

int main()
{
    int i,j,n,t,m;
    //freopen("output.txt","w",stdout);
    cin>>t;
    while(t--)
    {
        set<int>answer;
        cin>>m;
        point p1,q1,p2,q2,r;
        line l1,l2;
        priority_queue<event_point>pq;
        /*VL will hold points of line segment.first of the pair is left most and
        second one is right most.If vertical line then first topmost then bottom
        */
        vector<pair<point,point> >VL;
        VL.resize(m+5);
        event_point ev1,intersection;
        line_segment ls,ls1,ls2;
        ans ANS;
        for(i=1;i<=m;i++)
        {
            cin>>p1.x>>p1.y>>p2.x>>p2.y;
            if(p1.x>p2.x)
            {
                swap(p1,p2);
            }
            else if(fabs(p1.x-p2.x)<EPS&&p1.y<p2.y)
            {
                swap(p1,p2);
            }
            VL[i]=make_pair(p1,p2);
            ev1.x=p1.x;
            ev1.y=p1.y;
            ev1.label=1;//start point
            ev1.corresponding_line=i;
            pq.push(ev1);
            ev1.x=p2.x;
            ev1.y=p2.y;
            ev1.label=3;//end point
            ev1.corresponding_line=i;
            pq.push(ev1);
        }
        set<line_segment>lset;
        set<line_segment>::iterator lsetitend,prev_point,next_point,above,below,it,tmp1,tmp2,tmp;
        set<ans>intersecting_lines;
        set<ans>::iterator ansit;
        pair<set<line_segment>::iterator,bool>sp;
        /*
            pair::first set to an iterator pointing to either the newly inserted element
            or to the equivalent element already in the set. The pair::second element in
            the pair is set to true if a new element was inserted or false if an equivalent
            element already existed. From C++ reference, return value of set insertion
        */
        while(!pq.empty())
        {
            event_point ev=pq.top();
            pq.pop();
            if(ev.label==1)//start point
            {
                ls.line_id=ev.corresponding_line;
                ls.y=ev.y;
                sp=lset.insert(ls);
                lsit[ls.line_id]=sp.first;
                if(sp.first!=lset.begin())
                {
                    prev_point=sp.first;
                    prev_point--;
                    i=(*prev_point).line_id;
                    j=(*sp.first).line_id;
                    p1=VL[i].first;
                    q1=VL[i].second;
                    p2=VL[j].first;
                    q2=VL[j].second;
                    if(doIntersect(p1,q1,p2,q2))
                    {
                        l1=point_to_line(p1,q1);
                        l2=point_to_line(p2,q2);
                        //must intersect and intersection point is set to r
                        does_intersect(l1,l2,&r);
                        ANS.intersecting_point=r;
                        if(i>j)
                        swap(i,j);
                        ANS.line1=i;
                        ANS.line2=j;
                        intersecting_lines.insert(ANS);
                        intersection.label=2;
                        intersection.line1=i;
                        intersection.line2=j;
                        intersection.x=r.x;
                        intersection.y=r.y;
                        pq.push(intersection);
                    }
                }
                lsetitend=lset.end();
                lsetitend--;
                if(sp.first!=lsetitend)
                {
                    next_point=sp.first;
                    next_point++;
                    i=(*next_point).line_id;
                    j=(*sp.first).line_id;
                    p1=VL[i].first;
                    q1=VL[i].second;
                    p2=VL[j].first;
                    q2=VL[j].second;
                    if(doIntersect(p1,q1,p2,q2))
                    {
                        l1=point_to_line(p1,q1);
                        l2=point_to_line(p2,q2);
                        //must intersect and intersection point is set to r
                        does_intersect(l1,l2,&r);
                        ANS.intersecting_point=r;
                        if(i>j)
                        swap(i,j);
                        ANS.line1=i;
                        ANS.line2=j;
                        intersecting_lines.insert(ANS);
                        event_point intersection;
                        intersection.label=2;
                        intersection.line1=i;
                        intersection.line2=j;
                        intersection.x=r.x;
                        intersection.y=r.y;
                        pq.push(intersection);
                    }
                }
        }
        else if(ev.label==2)
        {
            i=ev.line1;
            j=ev.line2;
            above=lsit[i];
            below=lsit[j];
            ls1=*above;
            ls2=*below;
            // they were sorted according to start point y co ordinate now they will be sorted according to right end point y coordinate
            ls1.y=VL[i].second.y;
            ls2.y=VL[j].second.y;
            lset.erase(above);
            if(above!=below)
            lset.erase(below);
            sp=lset.insert(ls1);
            above=sp.first;
            lsit[i]=sp.first;
            sp=lset.insert(ls2);
            lsit[j]=sp.first;
            below=sp.first;
            if(above!=lset.begin())
            {
                tmp1=above;
                tmp1--;
                ls1=*tmp1;
                ls2=*above;
                i=ls1.line_id;
                j=ls2.line_id;
                p1=VL[i].first;
                q1=VL[i].second;
                p2=VL[j].first;
                q2=VL[j].second;
                if(doIntersect(p1,q1,p2,q2))
                {
                    l1=point_to_line(p1,q1);
                    l2=point_to_line(p2,q2);
                    //must intersect and intersection point is set to r
                    does_intersect(l1,l2,&r);
                    ANS.intersecting_point=r;
                    if(i>j)
                        swap(i,j);
                    ANS.line1=i;
                    ANS.line2=j;
                    if(intersecting_lines.find(ANS)==intersecting_lines.end())
                    {
                        intersecting_lines.insert(ANS);
                        intersection.label=2;
                        intersection.line1=i;
                        intersection.line2=j;
                        intersection.x=r.x;
                        intersection.y=r.y;
                        pq.push(intersection);
                    }
                }
            }
            lsetitend=lset.end();
            lsetitend--;
            if(above!=lsetitend)
            {
                tmp1=above;
                tmp1++;
                ls1=*tmp1;
                ls2=*above;
                i=ls1.line_id;
                j=ls2.line_id;
                p1=VL[i].first;
                q1=VL[i].second;
                p2=VL[j].first;
                q2=VL[j].second;
                if(doIntersect(p1,q1,p2,q2))
                {
                    l1=point_to_line(p1,q1);
                    l2=point_to_line(p2,q2);
                    //must intersect and intersection point is set to r
                    does_intersect(l1,l2,&r);
                    ANS.intersecting_point=r;
                    if(i>j)
                        swap(i,j);
                    ANS.line1=i;
                    ANS.line2=j;
                    if(intersecting_lines.find(ANS)==intersecting_lines.end())
                    {
                        intersecting_lines.insert(ANS);
                        intersection.label=2;
                        intersection.line1=i;
                        intersection.line2=j;
                        intersection.x=r.x;
                        intersection.y=r.y;
                        pq.push(intersection);
                    }
                }
            }
            if(below!=lset.begin())
            {
                tmp1=below;
                tmp1--;
                ls1=*tmp1;
                ls2=*below;
                i=ls1.line_id;
                j=ls2.line_id;
                p1=VL[i].first;
                q1=VL[i].second;
                p2=VL[j].first;
                q2=VL[j].second;
                if(doIntersect(p1,q1,p2,q2))
                {
                    line l1,l2;
                    l1=point_to_line(p1,q1);
                    l2=point_to_line(p2,q2);
                    point r;
                    //must intersect and intersection point is set to r
                    does_intersect(l1,l2,&r);
                    ans ANS;
                    ANS.intersecting_point=r;
                    if(i>j)
                        swap(i,j);
                    ANS.line1=i;
                    ANS.line2=j;
                    if(intersecting_lines.find(ANS)==intersecting_lines.end())
                    {
                        intersecting_lines.insert(ANS);
                        event_point intersection;
                        intersection.label=2;
                        intersection.line1=i;
                        intersection.line2=j;
                        intersection.x=r.x;
                        intersection.y=r.y;
                        pq.push(intersection);
                    }
                }
            }
            lsetitend=lset.end();
            lsetitend--;
            if(below!=lsetitend)
            {
                tmp1=below;
                tmp1++;
                ls1=*tmp1;
                ls2=*below;
                i=ls1.line_id;
                j=ls2.line_id;
                p1=VL[i].first;
                q1=VL[i].second;
                p2=VL[j].first;
                q2=VL[j].second;
                if(doIntersect(p1,q1,p2,q2))
                {
                    l1=point_to_line(p1,q1);
                    l2=point_to_line(p2,q2);
                    point r;
                    //must intersect and intersection point is set to r
                    does_intersect(l1,l2,&r);
                    ANS.intersecting_point=r;
                    if(i>j)
                        swap(i,j);
                    ANS.line1=i;
                    ANS.line2=j;
                    if(intersecting_lines.find(ANS)==intersecting_lines.end())
                    {
                        intersecting_lines.insert(ANS);
                        event_point intersection;
                        intersection.label=2;
                        intersection.line1=i;
                        intersection.line2=j;
                        intersection.x=r.x;
                        intersection.y=r.y;
                        pq.push(intersection);
                    }
                }
            }
        }
        else if(ev.label==3)
        {
            int sz=lset.size();
            i=0;
            i=ev.corresponding_line;
            tmp=lsit[i];
            lsetitend=lset.end();
            lsetitend--;
            if(tmp!=lset.begin()&&tmp!=lsetitend)
            {
                lset.erase(tmp);
                above=tmp;
                above--;
                below=tmp;
                below++;
                ls1=*above;
                ls2=*below;
                i=ls1.line_id;
                j=ls2.line_id;
                p1=VL[i].first;
                q1=VL[i].second;
                p2=VL[j].first;
                q2=VL[j].second;
                if(doIntersect(p1,q1,p2,q2))
                {
                    l1=point_to_line(p1,q1);
                    l2=point_to_line(p2,q2);
                    point r;
                    //must intersect and intersection point is set to r
                    does_intersect(l1,l2,&r);
                    //ANS.intersecting_point=r;
                    if(i>j)
                        swap(i,j);
                    ANS.line1=i;
                    ANS.line2=j;
                    if(intersecting_lines.find(ANS)==intersecting_lines.end())
                    {
                        intersecting_lines.insert(ANS);
                        event_point intersection;
                        intersection.label=2;
                        intersection.line1=i;
                        intersection.line2=j;
                        intersection.x=r.x;
                        intersection.y=r.y;
                        pq.push(intersection);
                    }
                }
            }
            else
            {
                lset.erase(tmp);
            }
        }
    }
    for(ansit=intersecting_lines.begin();ansit!=intersecting_lines.end();ansit++)
    {
        ANS=*ansit;
        answer.insert(ANS.line1);
        answer.insert(ANS.line2);
    }
    //cout<<answer.size()<<endl;
    cout<<m-answer.size()<<endl;
    }
    return 0;
}

metaphysis
Experienced poster
Posts: 130
Joined: Wed May 18, 2011 3:04 pm

Re: 11343 - Isolated Segments

Post by metaphysis » Thu Dec 07, 2017 2:32 pm

Test data generator.

Code: Select all

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char *argv[])
{
    srand(time(NULL));

    cout << 1000 << '\n';
    for (int c = 1; c <= 1000; c++)
    {
        int M = rand() % 101;
        cout << M << '\n';
        for (int i = 0; i < M; i++)
        {
            int px = rand() % 1000, py = rand() % 1000;
            int ex = rand() % 1000, ey = rand() % 1000;
            if (rand() % 2) px *= -1;
            if (rand() % 2) py *= -1;
            if (rand() % 2) ex *= -1;
            if (rand() % 2) ey *= -1;
            cout << px << ' ' << py << ' ' << ex << ' ' << ey << '\n';
        }
    }
    return 0;
}

Post Reply

Return to “Volume 113 (11300-11399)”