斜率在解题中的巧用

斜率在解题中的巧用

斜率这个概率很简单，描述了几何线的变化。恰当的运用它能让整个思维变得开阔。 51nod 1451 合法三角形 ​​​(1 ≤ n ≤ 2000)，表示点的数目。接下来n行，每行包含两个整数 xi, yi ( -100 ≤ xi, yi ≤ 100)，表示第i个点的坐标。输入保证点是两两不同的。

Output

输出合法的三角形数目。

不用三边长关系来判断能否构成三角形，直接考虑各个点的组合。

最简单的情况下，选三个不同的点可以组成三角形.

一般情况下，存在三点共线的情况，除去它们。（注：斜率相等不一定共线啊，但是共线一定斜率相等）

抓住共线一定斜率相等的特点不断排除不该有的三角形。

拓展：三重循环的执行次数等于 n(n-1)(n-2)/6，推广，一个长度为n的m重循环的执行次数就是：

（组合学的角度更好理解）

#include #include #include #include using namespace std;const int N=2e3+10,M=4e6+10;const double eps=1e-7;typedef long long LL;struct point{ double x,y;}p[N];double k[M];double getk(point a,point b){ if(a.x==b.x) return 400; // 正无穷 return (b.y-a.y)/(b.x-a.x);}int cmp(double a,double b){ return a-b<-eps;}int main(){ //freopen("cin.txt","r",stdin); LL n; while(cin>>n){ for(int i=0;i

codeforce 514B - Han Solo and Lazer Gun

​​set

#include #include #include #include using namespace std;const double PI=acos(-1.0);const int N=1e3+10;struct point{ int x,y;}p[N];double k[N];int main(){ double INF=tan(PI/2); int n,x0,y0; while(~scanf("%d%d%d",&n,&x0,&y0)){ int top=0; for(int i=0;i mp(k,k+top); printf("%d\n",mp.size()); } return 0;}

hdu 4310 Hero

​​输出最小值。

分析：也含有比值（斜率的思想）。不过要处理一下，

#include #include #include using namespace std;struct node{ int d,h;}p[25];int cmp(node t1,node t2){ return t1.d*t2.h>t1.h*t2.d;}int main(){ int n; while(cin>>n){ for(int i=0;i

lydsy 2659 [Beijing wc2012]算不出的算式

​​http://lydsy.com/JudgeOnline/problem.php?id=2659​​

大意：求解式子

其中p和q是两个奇质数

分析：数形结合

k=q/p和k=p/q的两条直线关于y=x对称，

刚好可以看做小矩形的一部分S

所以，一般情况下和的结果就是小矩形的面积。 但是当p=q时，向下取整就是本身，所以还要再加上对角线段的长一次

#include #include using namespace std;typedef long long LL;int main(){ LL p,q; while(~scanf("%lld %lld",&p,&q)){ LL ans=(p/2)*(q/2); if(p==q) ans=ans+p/2; //再加上一次直线上的点 printf("%lld\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。