蓝桥杯刷题冲刺 | 倒计时8天

作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

1.三角形的面积

• 题目

  链接： 三角形的面积 - 蓝桥云课 (lanqiao.cn)

  平面直角坐标系中有一个三角形， 请你求出它的面积。

  输入描述

  第一行输入一个 T ,代表测试数据量

  每组测试数据输入有三行，每行一个实数坐标 (x,y) 代表三角形三个顶点。

  1≤T≤$10^3$ ,−$10^5$≤x,y≤$10^5$

  输出描述

  输出一个实数表示三角形面积。结果保留2位小数，误差不超过 $10^{-2}$

  输入输出样例

  示例 1

  输入

  2
  0 1
  1 0
  1 1
  0 0
  1 1
  2 2
  

  输出

  0.50
  0.00
  

• 第一次 AC 100% 坐标公式

  #include<bits/stdc++.h>
  using namespace std;int main()
  {int n;cin>>n;double x1,y1,x2,y2,x3,y3;double S;while(n--){cin>>x1>>y1>>x2>>y2>>x3>>y3;  //公式背过S=fabs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)*1.0/2;  //这里，abs的使用，面积没有负的printf("%.2f\n",S);}return 0;} 
  

• 题解二 海伦公式----边长

  #include<bits/stdc++.h>
  using namespace std;int main()
  {int n;cin>>n;long double x1,y1,x2,y2,x3,y3;long double a,b,c;long double S;while(n--){cin>>x1>>y1>>x2>>y2>>x3>>y3;//算出来 三个边长 long double a=sqrt(pow(x1-x2,2)+pow(y1-y2,2));long double b=sqrt(pow(x1-x3,2)+pow(y1-y3,2));long double c=sqrt(pow(x2-x3,2)+pow(y2-y3,2));//海伦公式 long double p=(a+b+c)/2;S=sqrt(p*(p-a)*(p-b)*(p-c));   //背过printf("%.2Lf\n",S);  //这里，输出 Lf}return 0;} 
  

  double 竟然不能用，使用 long doule 才可以

  double占用8个字节，long double占用16个字节，因此long double的精度更高，但也会占用更多的内存空间。

  一般使用double就可以满足需求，只有在需要更高精度的计算时才会使用long double。

  long double 输出用%Lf

  这个题为什么用 long double 记住就行 T-T

• 反思

  1. 把三角形的公式搞定
  2. 输出格式，\n以及有小数点的限制，注意！！
  3. 绝对值 整数时，使用 abs；浮点数，使用 fabs

  • 上述两种方法，一个边长，一个坐标，应该解决三角形面积就够了

2.图中点的层次

• 题目

  链接： 847. 图中点的层次 - AcWing题库

  给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。

  所有边的长度都是 1，点的编号为 1∼n。

  请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。

  输入格式

  第一行包含两个整数 n 和 m。

  接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。

  输出格式

  输出一个整数，表示 1 号点到 n 号点的最短距离。

  数据范围

  1≤n,m≤$10^5$

  输入样例：

  4 5
  1 2
  2 3
  3 4
  1 3
  1 4
  

  输出样例：

  1
  

• 第一次 AC 100%

  #include<bits/stdc++.h>
  using namespace std;const int N=1e5+10;int n,m;
  int h[N],e[N],ne[N],idx;
  int d[N];void add(int a,int b)
  {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
  }int bfs()
  {memset(d,-1,sizeof d);d[1]=0;queue<int>  q;q.push(1);while(q.size()){int t=q.front();q.pop();for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(d[j]==-1){d[j]=d[t]+1;q.push(j);}}}return d[n];
  }int main()
  {cin>>n>>m;memset(h,-1,sizeof h);  //!!!!!!!!!! 记得写上while(m--){int a,b;cin>>a>>b;add(a,b);}cout<<bfs();return 0;
  }
  

• 反思

  写一道模板题水一下，不定时复习暴搜

  使用邻接表的时候 h 初始化 + add ，初始化别丢