UVa 12816 Isosceles Triangles-育师

摘要：给定平面上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个点，问这些点能组成多少个等腰三角形。
等腰三角形的定义是：恰好有两条边长度相等。三点共线不能构成三角形。

输入格式

输入包含多组测试用例。
每个测试用例第一行为一个整数NNN（1≤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)，其中i<j<ki < j < ki<j<k，对每个三元组执行以下步骤：

计算叉积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)，对于N=100N=100N=100完全可行，空间复杂度O(N)O(N)O(N)存储点集。

代码实现

// Isosceles Triangles// UVa ID: 1816// Verdict: Accepted// Submission Date: 2026-07-13// UVa Run Time: 0.010s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structPoint{doublex,y;};doubledist(constPoint&a,constPoint&b){doubledx=a.x-b.x,dy=a.y-b.y;returnsqrt(dx*dx+dy*dy);}intmain(){intN;while(scanf("%d",&N)==1){vector<Point>pts(N);for(inti=0;i<N;++i)scanf("%lf %lf",&pts[i].x,&pts[i].y);intans=0;constdoubleEPS=1e-6;for(inti=0;i<N;++i)for(intj=i+1;j<N;++j)for(intk=j+1;k<N;++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;doubled12=dist(pts[i],pts[j]);doubled13=dist(pts[i],pts[k]);doubled23=dist(pts[j],pts[k]);inteq=0;if(fabs(d12-d13)<EPS)++eq;if(fabs(d12-d23)<EPS)++eq;if(fabs(d13-d23)<EPS)++eq;if(eq==1)++ans;}printf("%d\n",ans);}return0;}