How to solve this problem?About right-angele.

[firstfire]

http://acm.zju.edu.cn/show_problem.php?pid=1580

My program always TLE.

#include <iostream.h>
#define N 1000

struct Point
{double x,y;
}p[N];

int RightAngledCount(int i, int j, int k)
{
int ReturnValue=0;
ReturnValue=((p[i].x-p[j].x)*(p[k].x-p[j].x)+(p[i].y-p[j].y)*(p[k].y-p[j].y));
ReturnValue*=((p[j].x-p[i].x)*(p[k].x-p[i].x)+(p[j].y-p[i].y)*(p[k].y-p[i].y));
ReturnValue*=((p[j].x-p[k].x)*(p[i].x-p[k].x)+(p[j].y-p[k].y)*(p[i].y-p[k].y));
return !ReturnValue;
}

int main()
{
int n,i,j,k,count;

while(cin>>n)
{
for(i=0,count=0;i<n;i++)
cin>>p[i].x>>p[i].y;

for(j=0;j<n;j++)
for(i=j+1;i<n;i++)
for(k=i+1;k<n;k++)
count+=RightAngledCount(i,j,k);//for

cout<<count<<endl;
}//while


return 1;
}

[Yves M]

Your program is O(N^3) and that's probably too slow, since the execution time limit is 5 seconds.

My idea would be to construct a vector of the N^2 line segments joining two points. Then sort that vector according to the angle of the line segment with respect to the (0,0) point. Now you can go through the vector linearly with two pointers. The first pointer will be the segment that you are trying to add to a right-angle triangle and the second pointer will point to a segment that has an orientation of 90 degrees with respect to the first one. This step is linear in N^2.

Overall that solution would be O(N^2 Log(N)), i.e. about 300 times faster.

[firstfire]

Thanks a lot .I think I know how to solve the problem now.