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 this code below gives the correct result. I'm not sure
whether it's the same as yours or not.
#include <vector>
#include <algorithm>
using namespace std;
struct Chord
{
float theta1, theta2;
};
class EndPoint
{
private:
float theta_;
int idx_;
public:
EndPoint(void) { }
EndPoint(float t, bool start, int i)
: theta_(t), idx_(start ? i : -i - 1) { }
float theta(void) const { return(theta_); }
// If negative, end endpoint, real idx is -idx - 1 .
int idx(void) const { return(idx_); }
};
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, i);
ep[2 * i + 1] = EndPoint(v[i].theta2, !start1, i);
}
sort(ep.begin(), ep.end());
vector<int> count(v.size());
int endNotSeen = 0, tot = 0;
for (i = 0; i < (2 * v.size()); i++)
{
if (ep[i].idx() >= 0)
count[ep[i].idx()] = ++endNotSeen;
else
tot += (endNotSeen--) - count[-ep[i].idx() - 1];
}
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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
