摘要给定平面上NNN个点N≤100N \le 100N≤100统计能构成的等腰三角形数量其中等腰要求恰好两条边相等等边三角形不计入三点共线也不构成三角形。由于数据规模很小三点组合数最多约1.6×1051.6 \times 10^51.6×105可直接O(N3)O(N^3)O(N3)暴力枚举每个三元组先用叉积排除共线情况再用浮点数计算三条边长借助10−610^{-6}10−6的误差阈值统计三对边中相等的对数恰好为111时答案加一。题目描述给定平面上NNN个点问这些点能组成多少个等腰三角形。等腰三角形的定义是恰好有两条边长度相等。三点共线不能构成三角形。输入格式输入包含多组测试用例。每个测试用例第一行为一个整数NNN1≤N≤1001 \le N \le 1001≤N≤100接下来NNN行每行两个整数Xi,YiX_i, Y_iXi,Yi−100≤Xi,Yi≤100-100 \le X_i, Y_i \le 100−100≤Xi,Yi≤100表示点的坐标。输入以EOF\texttt{EOF}EOF结束。输出格式对于每个测试用例输出一行一个整数表示等腰三角形的总数。样例输入6 -4 1 -3 3 -2 1 -2 0 -1 1 1 -1 3 -4 1 -2 1 -1 1输出4 0题目分析本题数据规模很小N≤100N \le 100N≤100所有三点组合数为(1003)161700\binom{100}{3} 161700(3100)161700完全可以在O(N3)O(N^3)O(N3)时间内暴力枚举每个三元组并判定。对于任意三个点首先需要判断它们是否共线。若共线则面积为000不能构成三角形。共线判定可使用叉积设三点为A(x1,y1)A(x_1,y_1)A(x1,y1)B(x2,y2)B(x_2,y_2)B(x2,y2)C(x3,y3)C(x_3,y_3)C(x3,y3)则叉积cross(x2−x1)(y3−y1)−(y2−y1)(x3−x1) \textit{cross} (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1)cross(x2−x1)(y3−y1)−(y2−y1)(x3−x1)若∣cross∣10−6|\textit{cross}| 10^{-6}∣cross∣10−6则认为三点共线。若不共线则计算三条边的长度欧氏距离使用浮点数double\texttt{double}double存储。等腰三角形的判定标准是恰好有两边长度相等。注意等边三角形三边相等不符合题意因为等腰要求“恰好”两条边相等。因此我们需要统计三对长度比较中相等的对数。若相等对数为111则三角形是等腰非等边计数加一。由于坐标都是整数边长可能为无理数因此比较时需要允许误差。题目要求两个长度La,LbL_a, L_bLa,Lb视为相等当且仅当∣La−Lb∣10−6|L_a - L_b| 10^{-6}∣La−Lb∣10−6。解题思路直接枚举所有三元组(i,j,k)(i, j, k)(i,j,k)其中ijki j kijk对每个三元组执行以下步骤计算叉积cross\textit{cross}cross若∣cross∣ϵ|\textit{cross}| \epsilon∣cross∣ϵ则三点共线跳过。计算三条边长d12,d13,d23d_{12}, d_{13}, d_{23}d12,d13,d23。统计三对长度比较中相等的次数若∣d12−d13∣ϵ|d_{12} - d_{13}| \epsilon∣d12−d13∣ϵ相等计数加一若∣d12−d23∣ϵ|d_{12} - d_{23}| \epsilon∣d12−d23∣ϵ相等计数加一若∣d13−d23∣ϵ|d_{13} - d_{23}| \epsilon∣d13−d23∣ϵ相等计数加一。若相等计数恰好为111则说明该三角形有且仅有一对边相等即恰有两边相等答案加一。该方法的时间复杂度为O(N3)O(N^3)O(N3)对于N100N100N100完全可行空间复杂度O(N)O(N)O(N)存储点集。代码实现// Isosceles Triangles// UVa ID: 1816// Verdict: Accepted// Submission Date: 2026-07-13// UVa Run Time: 0.010s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structPoint{doublex,y;};doubledist(constPointa,constPointb){doubledxa.x-b.x,dya.y-b.y;returnsqrt(dx*dxdy*dy);}intmain(){intN;while(scanf(%d,N)1){vectorPointpts(N);for(inti0;iN;i)scanf(%lf %lf,pts[i].x,pts[i].y);intans0;constdoubleEPS1e-6;for(inti0;iN;i)for(intji1;jN;j)for(intkj1;kN;k){// 叉积判断共线doublecross(pts[j].x-pts[i].x)*(pts[k].y-pts[i].y)-(pts[j].y-pts[i].y)*(pts[k].x-pts[i].x);if(fabs(cross)EPS)continue;doubled12dist(pts[i],pts[j]);doubled13dist(pts[i],pts[k]);doubled23dist(pts[j],pts[k]);inteq0;if(fabs(d12-d13)EPS)eq;if(fabs(d12-d23)EPS)eq;if(fabs(d13-d23)EPS)eq;if(eq1)ans;}printf(%d\n,ans);}return0;}总结本题是一道经典的几何计数问题由于数据规模小暴力枚举所有三点组合是最高效且最直接的做法。关键点在于利用叉积排除共线情况使用浮点数及误差阈值比较边长避免精度问题严格区分等腰三角形恰好一对等边与等边三角形三边相等只统计相等对数为111的情况。该解法思路清晰代码简洁时间复杂度O(N3)O(N^3)O(N3)足以应对N100N100N100的限制。在实际比赛中此类小数据题目应优先考虑暴力枚举确保正确性。
