[algogeeks] Re: Chord Intersection

[W Karas]

Dhyanesh wrote:
> 1 ) Radially sort the all the points of each chord (start and end both ).
> 2 ) Start with the first start point. Have c=1, tot=0, done[1..n]=0
> 3 ) Till all points are done:
>    a ) If its a start point then
>         tot  = tot + c
>         c = c + 1
>          set done for this point 1
>      else if it is an end point of a start point processed then
>               c = c- 1;
>           set done for this point 1
> 4 ) Answer is tot.
>
> -Dhyanesh
>
> On 4/20/06, pramod <[EMAIL PROTECTED]> wrote:
> >
> > There are 'n' chords of a circle. How to find the number of pairs of
> > the chords which are intersecting in O(n log(n)) time. All the end
> > points of the chords are unique.

I think the code below is correct, not sure if its the same as yours
or not.

#include <vector>
#include <algorithm>

using namespace std;

struct Chord
  {
    float theta1, theta2;
  };

class EndPoint
  {
  private:
    float theta_;
    bool start_;

  public:
    EndPoint(void) { }

    EndPoint(float t, bool s)
      : theta_(t), start_(s)

    float theta(void) const { return(theta_); }

    bool start(void) const { return(start_); }

  };

inline bool operator < (EndPoint ep1, EndPoint ep2)
  { return(ep1.theta() < ep2.theta()); }

int crossCount(vector<Chord> &v)
  {
    vector<EndPoint> ep(2 * v.size());
    bool start1;
    int i;

    for (i = 0; i < v.size(); i++)
      {
        start1 = v[i].theta1 < v[i].theta2;
        ep[2 * i] = EndPoint(v[i].theta1, start1);
        ep[2 * i + 1] = EndPoint(v[i].theta2, !start1);
      }

    sort(ep.begin(), ep.end());

    int endNotSeen = 0, tot = 0;

    for (i = 0; i < (2 * v.size()); i++)
      {
        if (ep[i].start())
          tot -= endNotSeen++;
        else
          tot += --endNotSeen;
      }

    return(tot);
  }


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---