-
2021-05-31 20:38:17
向量OA(x1,y1),OB(x2,y2)double最多输出12位
平面叉积坐标表达式:S=x1*y2-x2*y1;要取绝对值哦;
若为平行四边形:y1=k1*x1+b1;y2=k1*x2+b2;y3=k2*x3+b3;y4=k2*x4+b4;
则:S=(b4-b3)*(b2-b1)/(k1-k2);注意也要取绝对值;
例题:
#include<stdio.h> #include<math.h> int main(){ double k1,k2,b1,b2,b3,b4,price,s,ans; int T; scanf("%d",&T); while(T--){ scanf("%lf%lf%lf%lf%lf%lf%lf",&k1,&k2,&b1,&b2,&b3,&b4,&price); s=(b4-b3)*(b2-b1)/(k1-k2); ans=s*price; ans=fabs(ans); printf("%.10lf\n",ans); } return 0; }
更多相关内容 -
八年级数学下册第4章平行四边形4.6反证法作业设计新版浙教版
2021-09-09 21:52:03八年级数学下册第4章平行四边形4.6反证法作业设计新版浙教版 -
【数据结构】平行四边形数量
2022-01-06 17:57:38平行四边形个数,哈希表,散列题目描述:给一些散点,找出可以构成平行四边形的数量
输入
第一行是测试样本个数n<=100
接下来有n组数据,每组数据第一行是m<=400,表示接下来的点数,接下来有m行,每行有两个整数表示点坐标
输出
有n行,每行是每个样本的平行四边形个数
样例输入
2 6 0 0 2 0 4 0 1 1 3 1 5 1 7 -2 -1 8 9 5 7 1 1 4 8 2 0 9 8
样例输出
5 6
提示
注意四点共线不算平行四边形,使用哈希求解。
点可能有重复。比如A和A'重复且ABCD是平行四边形,这样算2个。
提示:平行四边形两对角线中点重合。(中点可转化为坐标和形式,避免因为/2需要引入小数运算)参考课上讲解的寻找正方形个数的代码。
提供哈希样例:key = (((mid[k].x) * 1000 + (mid[k].y) * 1234) % MD + MD) % MD; (MD=119997)
首先,讲一下寻找正方形个数的代码:
简而言之,给出两个点,那么能和这两个点组成正方形的点的位置是一定的,一共有四组。只要在已有点的哈希表里面找有没有这四组点就可以了。由于散列的查找复杂度是O(1),所以复杂度只集中在对点的两两遍历。
但是在平行四边形查找中,这个思想我一开始尝试了,但不太可行,因为两个点确定的平行四边形,要求另外两个点是平行且长度相等。其实可以类似地,通过三个点来确定平行四边形第四个点的坐标,但这样的时间复杂度就到O(n^3),在OJ里过不了,c
考虑题目中的提示:平行四边形两对角线中点重合。
其实差一些平行四边形的算法,用的也大多是这个方法,但是在本题中问题更加复杂:有点重合的情况,而且有平行的情况,这两个情况解决花了大力气。
最后我的解决方案是:把两俩遍历的中点存入哈希表。平行的情况,通过在每个中点结构体加入成员:斜率k,如果两个中点斜率一样且坐标重合,那么他们是平行线而不是平行四边形。点重合的情况通过在点结构体加入成员int times解决,只要在最后统计累加时,把times乘进去即可。
代码实现:
首先是哈希表的实现:
#define NL 1001 #define MD 199997 #define ADD 20010 int hash1[MD]; //输入k,根据p[k]点xy值,把k存入hash1表中对应的桶内 void hashing(int k) { // 线性试探法 int key = (((p[k].x ) * 1000 + (p[k].y) *1234) % MD +MD) % MD; while (hash1[key] > 0) key = (key + 1) % MD; hash1[key] = k; } //输入po点,根据po找到存在hash1表中的点位置,如果找到且点一样则返回1 int searching(POINT po) { // 线性试探法 int key = (((po.x ) * 1000 + (po.y) *1234) % MD +MD) % MD; while (hash1[key] > 0) { int t = hash1[key]; if (p[t].x == po.x && p[t].y == po.y) return 1; key = (key + 1) % MD; } return 0; }
使用哈希样例:key = (((mid[k].x) * 1000 + (mid[k].y) * 1234) % MD + MD) % MD; (MD=119997)
这里两个函数,一共计算hash值,存入桶内,另一个是查找函数,看桶内是否有该坐标点。
接下来是定义点结构体:
struct POINT { int x, y; int times=1; }p[NL]; struct midPOINT { //中点结构体,坐标和斜率 //如果坐标、斜率都相同,则是共线四点 int x, y; int times=1; double k; }; bool cmp(midPOINT a,midPOINT b) { if(a.x==b.x) if(a.y==b.y) return a.k<b.k; else return a.y<b.y; return a.x<b.x; } vector<midPOINT> midp;//存储中点坐标的向量
如上所述,中点结构体多了times变量和k变量。
这里重载了cmp函数,是因为打算用<algorithm>里面的向量排序算法,懒得自己写快速排序了。把中点向量设置为全局变量,是因为方便一些主函数外的函数调用,参数表改得太麻烦了。
times变量设置为1,每次有重复的点加进来,times++即可;
void timesadd(POINT po){ int key = (((po.x ) * 1000 + (po.y) *1234) % MD +MD) % MD;//找到 while (hash1[key] > 0) { int t = hash1[key]; if (p[t].x == po.x && p[t].y == po.y) {p[t].times++; return;} key = (key + 1) % MD; } }
这里图方便可以调用上面的searching函数,但考虑到时间复杂度还是重新实现了一遍searching过程。
最后是主函数:
int main(){ int m; scanf("%d", &m); int *result = new int[m]; int n; for(int ii=0;ii<m;ii++){ scanf("%d", &n); if (!n) break; memset(hash1, -1, sizeof(hash1)); for (int i = 1; i<=n; i++) { scanf("%d%d", &p[i].x, &p[i].y); if(searching(p[i])) //如果在已有点找到相同点 { //则该点times++ timesadd(p[i]); i--;n--; } else hashing(i); //如果没有相同点,则建立散列表 } int sum = 0; midPOINT dr1; //int ok1, ok2; for (int i = 1; i<=n; i++) { for (int j = i + 1; j<=n; j++) { dr1.y = p[i].y + p[j].y; dr1.x = p[j].x + p[i].x; // 中点坐标*2 dr1.k= p[i].x == p[j].x ?(double)MD :((double)p[i].y - (double)p[j].y)/((double)p[i].x - (double)p[j].x); dr1.times=p[i].times*p[j].times; midp.push_back(dr1); //cout<<"point: "<<p[i].x<<","<<p[i].y<<","<<p[i].times<<" "<<p[j].x<<","<<p[j].y<<","<<p[j].times;cout<<endl; //cout<<"midpoint: "<<dr1.x<<","<<dr1.y<<","<<dr1.k<<" ";cout<<endl; } } sort(midp.begin(),midp.end(),cmp); // for (int i = 0; i<midp.size(); i++) // {cout<<"point: "<<midp[i].x<<","<<midp[i].y<<","<<midp[i].k<<","<<midp[i].times;cout<<endl;} //向量排序、遍历、相同求和 int num=1,eqnum=1; for(int i=0;i<midp.size()-1;i++) { if(midp[i].x==midp[i+1].x&&midp[i].y==midp[i+1].y) num++; else if(num==1) ; else { int low=i-num+1,high=i; for(int kk=low;kk<high;kk++) for(int jj=kk+1;jj<=high;jj++) sum+=midp[jj].times*midp[kk].times; num=1; } if(midp[i].x==midp[i+1].x&&midp[i].y==midp[i+1].y&&midp[i].k==midp[i+1].k)eqnum++; else if(eqnum==1) ; else { int low=i-eqnum+1,high=i; for(int kk=low;kk<high;kk++) for(int jj=kk+1;jj<=high;jj++) sum-=midp[jj].times*midp[kk].times; eqnum=1; } //cout<<eqnum<<endl; //cout<<"point: "<<midp[i].x<<","<<midp[i].y<<","<<midp[i].k<<","<<midp[i].times<<endl; //cout<<"sum: "<<sum<<endl; } result[ii]=sum; midp.clear(); for(int i = 1; i<=n; i++) p[i].times=1; } for (int j = 0; j<m; j++) cout<<result[j]<<endl; cin>>n; return 0; }
第一步,初始化、建立哈希表,更新times值。
第二部,遍历中点,存入向量;
第三步,计算平行四边形个数。
两个难点问题:点重合、平行线,都是在主函数里解决的。
点重合是在建立哈希表的时候,如果以及存在该点,那么直接times++,不再插入点,而在之后中点和平行四边形下的计算中,times直接取乘积即可。这很容易理解:A点重合x1次,B点重合x2次,那么它们的中点(A+B)(省事儿,不除以二了,结果一样的)一共有x1*x2种组合,与另外的中点(C+D)如果能够组成平行四边形的话,两个中点的times乘积就是平行四边形的组合情况。
平行线的情况在最后计算统计的for循环里面解决。之前考虑过建立m个重合中点,m1个平行重点情况下的平行四边形个数递推公式,也推出来了,但是后面引入times解决重合点问题后,递推公式就不适用了。所以这里直接用遍历的方式找到多个重合中点的情况下,可能的平行四边形组合个数,平行线的直接在总数里面减去即可。
相较于不添加times变量,直接遍历计算的方法,使用times在点重合量大的情况下有时间和空间优势。例如n个点,m个重合,那么算法的复杂度是(n-m)^2,m越大优势越明显。当然,劣势是多了个变量,理解起来更困难,在m较小时也增加开销。
ps:这个代码是jqs老师2021-2022秋季学期数据结构课程OJ作业,如果看到有一样的代码是我本人写的,不是抄袭,老师助教明察。同学们理性参考。
-
平行四边形的周长公式
2021-05-25 04:00:56平行四边形的周长公式平行四边形的周长等于(长边(a)+短边(b))乘以2。计算公式L=2*(a+b) ,其中a表示长边,b表示短边,L表示周长,如图所示:如图所示如果知道a,h,和角度α也可以计算出平行四边行的周长,图中b=h/sin...平行四边形的周长公式
平行四边形的周长等于(长边(a)+短边(b))乘以2。计算公式L=2*(a+b) ,其中a表示长边,b表示短边,L表示周长,如图所示:
如图所示如果知道a,h,和角度α也可以计算出平行四边行的周长,图中b=h/sinα,所以L=2*(h/sinα+a),这里计算b用到的时直角三角形的斜边公式。如已知一条直角边和一个锐角,可用直角三角函数计算斜边。sinA=∠A的对边/斜边。
平行四边形的判定
1、两组对边分别平行的四边形是平行四边形(定义判定法);
2、一组对边平行且相等的四边形是平行四边形;
3、两组对边分别相等的四边形是平行四边形;
4、两组对角分别相等的四边形是平行四边形;
5、对角线互相平分的四边形是平行四边形;
平行四边形的特性
a.两组对边分别相等.
b.两组对角分别相等
c.邻角互补(角度之和为180度)
d.平行边间的高距离处处相等
e.平行四边形的对角线互相平分
f.连接任意四边形各边的中点所得图形是平行四边形
g.平行四边形的面积等于底和高的积(可视为矩形)
h.过平行四边形对角线交点的直线,将平行四边形分成全等的两部分图形
i.平行四边形是中心对称图形,对称中心是两对角线的交点.
j.平行四边形对角线把平行四边形面积分成四等份
k.平行四边形不是轴对称图形,但平行四边形是中心对称图形。矩形和菱形是轴对称图形。注:正方形,矩形以及菱形也是一种特殊的平行四边形,三者具有平行四边形的性质。
l.平行四边形ABCD中(如图)E为AB的中点,则AC和DE互相三等分,一般地,若E为AB上靠近A的n等分点,则AC和DE互相(n+1)等分。
m.平行四边形ABCD中,AC、BD是平行四边形ABCD的对角线,则各四边的平方和等于对角线的平方和。
n.平行四边形中,两条在不同对边上的高所组成的夹角,较小的角等于平行四边形中较小的角,较大的角等于平行四边形中较大的角。
平行四边形的周长计算器
平行四边形周长计算器
侧边 (b)
面积(S)
计算得出
底边 (a)
周长(P)
计算得出
高度 (h)
短对角线
计算得出
角 (θ)
弧度角度ππ/3
长对角线
计算得出
-
运用合作学习法进行平行四边形性质的教学尝试.doc
2021-11-10 08:06:35运用合作学习法进行平行四边形性质的教学尝试.doc -
输出平行四边形
2020-07-25 06:36:21//输出平行四边形 public class CopyOfPringRectangle { public static void main(String[] args) { //输出一行空格+星星 for (int i = 1; i <= 5; i++) { //输出一行里的空格 /** * 行i 空格5-i ...//输出平行四边形 public class CopyOfPringRectangle { public static void main(String[] args) { //输出一行空格+星星 for (int i = 1; i <= 5; i++) { //输出一行里的空格 /** * 行i 空格5-i * 第1行4个空格 * 第2行3个空格 * 第3行2个空格 * 第4行1个空格 * 第5行0个空格 */ for (int j = 1; j <= 5-i; j++) { System.out.print(" "); } //输出每行里的5列星星 for (int j = 1; j <= 5; j++) { System.out.print("*"); } //换到下一行 System.out.println(); } } }
-
八年级数学下册第十八章类比法学习平行四边形素材新版新人教版
2021-08-19 12:17:16八年级数学下册第十八章类比法学习平行四边形素材新版新人教版 -
程序流程图中通常用平行四边形表示分支结构
2021-03-10 07:36:16程序流程图中通常用平行四边形表示分支结构答:错DES的分组长度和有效密钥长度分别为( )答:64,56若采用2∶1的比例绘制一个直径为20的圆时,其绘图直径为40,标注尺寸为40。答:错某企业会计主管发现其部门内某会计... -
平行四边形(几何)题解
2020-05-23 23:17:44UPC NO.17场 问题 E: 平行四边形 时间限制: 3 Sec 内存限制: 128 MB 题目描述 求平面上n个点构成的平行四边形个数。 输入 一行一个数n。...1、两组对边分别平行的四边形是平行四边形(定义判定法) -
八年级数学下册第四章平行四边形4.6反证法导学案无答案新版浙教版
2021-09-09 22:03:21八年级数学下册第四章平行四边形4.6反证法导学案无答案新版浙教版 -
python 已知平行四边形三个点,求第四个点的案例
2020-12-04 12:30:53import numpy as np#已知平行四边形三个点,求第四个点#计算两点之间的距离def CalcEuclideanDistance(point1,point2):vec1 = np.array(point1)vec2 = np.array(point2)distance = np.linalg.norm(vec1 - vec2)... -
平行四边形(由*号输出平行四边形的图案)(坐标法)
2018-05-21 20:30:32#include <stdio.h>int main(void){ int i; int j; for(i=1;i<=5;i++) { printf("\n"); printf("\n"); for(j=1;j<=5;j++) { if(i==1&...j==3) { ... -
程序的运行流程图中,处理框用平行四边形来表示
2021-04-18 01:12:24【单选题】下列说法错误的是( ) 【单选题】四步触诊法检查的内容不包括( ) 【单选题】下列设备组中,完全属于输入设备的一组是____。 【问答题】我多年来一直关注阿根廷 经济的发展, 特别是 对 最近十五年来 阿根廷... -
web前端教程:用 CSS 实现三角形与平行四边形
2021-01-14 04:44:36下面就来看看这是如何实现的吧~第一种方法:利用border第一种方法是借助border属性 hack 出三角形,然后通过一个矩形拼接两个三角形最终制造出一个平行四边形。为什么使用border可以产生三角形呢?先来看看一张图片... -
用CSS实现三角形与平行四边形_html/css_WEB-ITnose
2021-06-12 04:20:04第二种方法:利用transform 使用transform来实现平行四边形的方法是我在逛去啊的时候看到的,效果大概是这个样子: 看到之后觉得好神奇啊,原来还可以只有平行四边形的外轮廓。(因为方法一只能创造填充效果的平行... -
51nod3102 小明爱平行四边形
2021-10-09 23:06:50小明非常喜欢平行四边形,有一天他得到了一些在二维平面内的点,现在小明想要知道从这些点里面有多少种挑法使得挑的这四个点可以组成平行四边形,保证不存在三个点在一条直线上,但是小明现在作业太多了,没有时间做... -
矢量合成和分解的方法--平行四边形法则.ppt
2020-12-19 13:16:13矢量合成和分解的方法--平行四边形法则* * * * * * * * * * * * * * * * 实验:蜡块的运动 问题?(1)什么叫合运动、分运动 (2)什么叫合速度、合位移 什么叫分速度、分位移 曲线运动是我们至今尚未研究过的复杂运动... -
三角形法则平行四边形法则
2018-04-25 11:38:13由|a|(矢量的模长)和|b|组成的平行四边形的对角线就是他们的合力,起点在A,结束点在B,大小是对角线的长度. 也即是说,平行四边性的对角线就是合力的大小和方向. 下面要说的是平行四边形的恒等式,先看下面的图: 当遇到... -
JAVA学习DAY3 - 循环 输出平行四边形,等腰三角形,菱形
2019-07-09 10:15:58JAVA输出平行四边形,等腰三角形,菱形 -
lightoj-1305 - Area of a Parallelogram【数学】【向量法求平行四边形面积】
2016-08-25 17:45:15题目链接: ... 1305 - Area of a Parallelogram ...A parallelogram is a quadrilateral with...涨姿势了:平行四边形的面积可以用两相邻向量求,公式就是 x1 * y2 - x2 * y1 这里有个详细的链接: 点击打开链接 -
用平移法演示得出平行四边形的面积公式
2017-04-24 13:13:13在学习平行四边形知识时,为了能更好地给学生们讲解其面积公式的由来,可以借助专业的几何绘图工具来制作动态课件,下面学习具体制作技巧。 几何绘图工具几何画板免费获取地址:... -
排列组合公式,用向量叉乘的办法计算平行四边形面积
2019-01-25 12:29:35struct Point{//两个点相减是向量,二维向量叉乘是平行四边形面积 int x,y; Point(int _x = 0, int _y = 0) :x(_x), y(_y) {} Point operator -(const Point &p)const { return Point(x - p.x, y - p.y)... -
平行四边形的面积公式是如何推导的?
2017-04-10 11:46:11平行四边形是中学时代要接触的一个基本几何图形,在学习该图形的几何知识时,最难掌握的就是推导它的面积公式,对于平行四边形的面积公式,可以这样理解:把平行四边形沿高剪开,拼成一个长方形,拼成长方形的长等于... -
区间dp及平行四边形优化
2021-03-05 19:51:36平行四边形优化的证明步骤: 1、证明cost()函数为凸 2、证明dp()为凸 3、证明决策单调性,即s[i][j-1]<=s[i][j]<=s[i+1][j](似乎只要满足四边形不等式的都满足决策单调性) 不同题型内的证法都不同。...