题目:等腰三角形 方法:枚举优化 题目链接:F-等腰三角形(hard)_牛客小白月赛69 (nowcoder.com)
思路:这题为基本判断等腰三角形数目的困难版本,简单版本的数据量仅仅为300,所以可以依次枚举三个点,在复杂度为n的三次方的情况下快速完成这道题,而困难版本将数据量提升到了3000的量级,所以必须将原先三次方的时间复杂度进行优化,这里用到优化的方式为枚举法优化至2维,思路为枚举n中的每一个点,将其作为等腰三角形的一个顶点,然后去枚举它的另外一个点,然后把它们二者同一距离的数量记录下来,这里统计答案的顺序很关键,先将记录的数量加入答案中,在更新记录的数量,这样才能保证结果的正确性,例如如果有三条边距离相等,所以这里答案为1+2=3,满足答案的正确性,处理共线问题的时候我们选择用了vis来记录,判断这个点是否为枚举j点的对称点,又由于对称的两边性,所以其实我们统计了两次,所以最终要将结果除以2才能知道我们枚举答案中有多少答案其实是共线的,即不满足题目要求需要减去,这里有个细节,判断对称点的时候由于用到的为减法,很有可能减完使vis数组越界,所以我们将所有的点,都设法移到第一象限,确保代码答案的普遍性,即,存入点的时候将x和y坐标的值均加了1500!!!
#include <bits/stdc++.h> #define ios \ ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr) #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,a,n) for(int i=n;i>=a;i--) #define lowbit(x) ((x) & - (x)) #define pb push_back #define SZ(v) ((int)v.size()) #define PI acos(-1) #define x first #define y second #define mem(a,b) memset((a),(b),sizeof(a)) using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; const ll LLINF=0x3f3f3f3f3f3f3f3fLL; const double eps=1e-6; const int MAX=2e5+10; const ll mod=1e9+7; /********************************* std-head *********************************/ int cnt[2000010],n,x[3010],y[2010],vis[3010][3010]; int dis(int i,int j){ return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); } int main(){ ios; int n; cin>>n; rep(i,1,n) { cin>>x[i]>>y[i]; vis[x[i]+1500][y[i]+1500]=1; } ll ans=0,line=0; rep(i,1,n){ rep(j,1,n){ if(i==j) continue; ans+=cnt[dis(i,j)]; //枚举优化关键,先累加在统计记录相同距离数据的数量 cnt[dis(i,j)]++; if(vis[2*x[i]-x[j]+1500][2*y[i]-y[j]+1500]==1) line++;//找到与x[j]y[j]共线的点,中点为x[i]y[i] } rep(j,1,n) { if(i==j) continue; cnt[dis(i,j)]=0; } } cout<<ans-line/2<<endl; }