打卡信奥刷题（3342）用C++实现信奥题 P9423 [蓝桥杯 2023 国 B] 数三角

P9423 [蓝桥杯 2023 国 B] 数三角

题目描述

小明在二维坐标系中放置了nnn个点，他想在其中选出一个包含三个点的子集，这三个点能组成三角形。然而这样的方案太多了，他决定只选择那些可以组成等腰三角形的方案。请帮他计算出一共有多少种选法可以组成等腰三角形？

输入格式

输入共n+1n + 1n+1行。

第一行为一个正整数nnn。

后面nnn行，每行两个整数xi,yix_i, y_ixi​,yi​表示第iii个点的坐标。

输出格式

输出共111行，一个整数。

输入输出样例 #1

输入 #1

5 1 4 1 0 2 1 1 2 0 1

输出 #1

5

说明/提示

样例说明

一共有555种选法：{2,3,4}\{2,3,4\}{2,3,4}、{3,4,5}\{3,4,5\}{3,4,5}、{4,5,2}\{4,5,2\}{4,5,2}、{5,2,3}\{5,2,3\}{5,2,3}、{1,3,5}\{1,3,5\}{1,3,5}。

评测用例规模与约定

• 对于20%20\%20%的数据，保证n≤200n \le 200n≤200。
• 对于100%100\%100%的数据，保证n≤2000n \le 2000n≤2000，0≤xi,yi≤1090 \le x_i, y_i \le 10^90≤xi​,yi​≤109。

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 E 题

C++实现

#include<iostream>#include<algorithm>#include<vector>#include<set>#include<utility>#include<map>usingll=longlongint;usingpii=std::pair<int,int>;constintMAXN=2e3+10;intn,ans;std::map<ll,int>dist;std::map<pii,int>mp;pii node[MAXN];llgetdist(inta,intb){intx1=node[a].first,y1=node[a].second,x2=node[b].first,y2=node[b].second;return1ll*(x2-x1)*(x2-x1)+1ll*(y2-y1)*(y2-y1);}piigetmid(pii a,pii b){if((a.first+b.first&1)||(a.second+b.second&1))return{-1,-1};elsereturn{a.first+b.first>>1,a.second+b.second>>1};}llC(intn,intm){// it seems that m cannot be greater than 2.if(m==1)returnn;elseif(m==2)returnn*(n-1)/2;}intmain(){std::cin>>n;for(inti=1;i<=n;i++){std::cin>>node[i].first>>node[i].second;mp[node[i]]++;}for(inti=1;i<=n;i++){dist.clear();for(intj=1;j<=n;j++){if(i==j)continue;dist[getdist(i,j)]++;}for(auto[d,cnt]:dist)ans+=C(cnt,2);}for(inti=1;i<=n;i++){for(intj=i+1;j<=n;j++)ans-=mp[getmid(node[i],node[j])];}std::cout<<ans;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容