<分区>
这是我正在研究的问题:
N points are placed in the coordinate plane.
Write a program that calculates how many ways we can choose three points so that they form a right triangle with legs parallel to the coordinate axes.
一个直角三角形有一个内角为 90 度。直角三角形的腿是它的两条短边。
这是我组织代码的方式。
对于每一点，我都检查了其他点。如果两个点具有匹配的 x 坐标和不同的 y 坐标，我会查看这些点以找到与新点具有相同 y 坐标和不同 x 的点。如果找到，我检查直角斜边是否在三个点中检查。
类似地，我对具有匹配的 y 坐标和不同的 x 的两个点重复了此修改。
该程序可以运行，但超出了时间复杂度，我不确定如何降低它。
这是我的代码:
double distwithoutroot(int x1, int y1, int x2, int y2) {
int xdist = pow((x2 - x1),2);
int ydist = pow((y2 - y1),2);
return xdist + ydist;
}
int main() {
int noofpoints;
cin >> noofpoints;
int xs[100000];
int ys[100000];
int count = 0;
for (int i = 0; i < noofpoints; i++) {
cin >> xs[i] >> ys[i];
}
for (int i = 0; i < noofpoints; i++) {
int main_x_point = xs[i];
int main_y_point = ys[i];
for (int j = 0; j < noofpoints; j++) {
int checkmatchx = xs[j];
int checkmatchy = ys[j];
if (main_x_point == checkmatchx && main_y_point != checkmatchy) {
for (int k = 0; k < noofpoints; k++) {
int secondcheckx = xs[k];
int secondchecky = ys[k];
if (checkmatchy == secondchecky && checkmatchx != secondcheckx) {
int hypotenus = distwithoutroot(main_x_point, main_y_point, secondcheckx, secondchecky);
int perpendicular = distwithoutroot(main_x_point, main_y_point, checkmatchx, checkmatchy);
int base = distwithoutroot(secondcheckx, secondchecky, checkmatchx, checkmatchy);
if (hypotenus== ( perpendicular+ base )) {
count += 1;
}
}
}
}
else if (main_y_point == checkmatchy && main_x_point != checkmatchx) {
for (int k = 0; k < noofpoints; k++) {
int secondcheckx = xs[k];
int secondchecky = ys[k];
if (checkmatchx == secondcheckx && checkmatchy != secondchecky) {
int hypotenus = distwithoutroot(main_x_point, main_y_point, secondcheckx, secondchecky);
int base = distwithoutroot(main_x_point, main_y_point, checkmatchx, checkmatchy);
int perpendicular = distwithoutroot(secondcheckx, secondchecky, checkmatchx, checkmatchy);
if (hypotenus == (perpendicular + base)) {
count += 1;
}
}
}
}
}
cout<<count;
}