网站代运营要多少费用吗,制作个人网站要多少钱,wordpress页面留言板,关于一学一做的短视频网站创作背景
看到一道题目有感而发想写一篇题解#xff0c;涉及的是一种逆向思维
桌面窗体重叠 - 洛谷https://www.luogu.com.cn/problem/U399827题目来源于《信息学奥赛课课通》 大致就是给一个长方形的左上顶点坐标#xff08;x1,y1#xff09;和右下顶点坐标#xff08;x…创作背景
看到一道题目有感而发想写一篇题解涉及的是一种逆向思维
桌面窗体重叠 - 洛谷https://www.luogu.com.cn/problem/U399827题目来源于《信息学奥赛课课通》 大致就是给一个长方形的左上顶点坐标x1,y1和右下顶点坐标x2,y2,一个长方形的左上顶点坐标x3,y3,右下顶点x4,y4然后判断这两个长方形是否重合。
思路呈现
1.一开始想的是从判断一个点是否在一个长方体内-判断一个长方形是否有点在另一个长方形中
代码如图显而易见的蠢 2.逆向思维的利用 判断两个长方形是否不重叠 判断两条线段是否不相交-判断两个长方形是否相交
比如说在x轴上我判断x10和x20的线段和x3,0和x4,0的线段是否相交的话要考虑四种情况因为不知道x1和x3的大小、x2和x4的大小
ifx3x1x4||x3x2x4||x1x3x2||x1x4x2
但是如果考虑不相交的话,最小值大于最大值最大值小于最小值就不想交了
ifx3x2||x4x1
显然简单了很多。
然后在y轴上考虑不相交
ify3y2||y4y1
只要在x、y轴上有一个判断不相交这这两个长方形也不会相交所以逻辑用或
合起来判断是否相交true为相交。
if(!(x3x2||x4x1||y3y2||y4y1))
再利用德·摩根定律
非(P 且 Q) (非 P) 或 (非 Q)
非(P 或 Q) (非 P) 且 (非 Q) 可以把条件更改为如下的条件
ifx3x2x4x1y3y2y4y1 完整代码
#includeiostream
#includecmath
#includecstring
#includealgorithm
using namespace std;
int main() {
int x1,x2,x3,x4,y1,y2,y3,y4;
cinx1x2y1y2x3x4y3y4;
if(x3x2x4x1y3y2y4y1){int leftmax(x1,x3);int rightmin(x2,x4);int topmax(y1,y3);int bottommin(y2,y4);
// coutleftendl;
// coutrightendl;
// couttopendl;
// coutbottomendl;int s(right - left) * (bottom - top);couts;
}else{cout0;
}
return 0;
}扩展
如何用编程N个人中解决至少两个人的生日在同一天的问题
1.至少两个人那要考虑2个人3个人......n个人生日在同一天的情况。就比较复杂。
2.使用了逆向思维的话
过来想,N个人生日全不相同的概率365/365*(364/365)*(363/365)*...*[(366n)/365]…………[即后N1个人与前面的人都不一样] 364!/[(365n)!·365^(N-1)]
第一个人的生日可以在任何一天第二个人的生日是除了第一个人生日那天外的任何一天....... 所以至少有两人是同一天生日的概率为1364!/[(365n)!·365^(N-1)].
