CodeForces 993A Two Squares(数学 几何)

 

https://codeforces.com/problemset/problem/993/A

CodeForces 993A Two Squares(数学 几何)

 

 

 CodeForces 993A Two Squares(数学 几何)

 

 

 CodeForces 993A Two Squares(数学 几何)

 

 

 CodeForces 993A Two Squares(数学 几何)

 

 

 CodeForces 993A Two Squares(数学 几何)

 

 

 

 

题意:

给你两个矩形,第一行是一个正面表示的矩形,第二个是一个旋转四十五度角的矩形,问这两个矩形是否相交

思路:

刚开始的想法:

因为题目数据范围很小,所以很容易想到的是暴力枚举每个矩形中的每个点,若有点既在第一个矩形又在第二个矩形内,则这两个矩形相交

不过既然是数学题,就最好不要暴力了

 

要知道,如果两个正方形相交,那么其中一个正方形的四个角至少有一个处于另一个正方形内,或者一个正方形的中心处于另一个正方形内。 

如果是正方形②的角在正方形①内的话,就很容易就可以判断,但是,如果是正方形①的角在正方形②内的话,就需要求出正方形②的边,然后根据点在直线的上下方关系来判断。

代码如下:

 1 #include "iostream"
 2 #include "algorithm"
 3 using namespace std;
 4 int main()
 5 {
 6     double nu,nd,nl,nr,mu,md,ml,mr,mx,my,x,y;//u,d,l,r,分别记录最上,最下,最左,最右的值,mx,my记录的是正方形②中心的坐标
 7     nu=nr=mu=mr=-105;//由于范围是-100~100,所以赋初值
 8     nd=nl=md=ml=105;
 9     for(int i=0;i<4;i++){
10         cin>>x>>y;
11         nd=min(nd,y);
12         nu=max(nu,y);
13         nl=min(nl,x);
14         nr=max(nr,x);
15     }
16     for(int i=0;i<4;i++){
17         cin>>x>>y;
18         md=min(md,y);
19         mu=max(mu,y);
20         ml=min(ml,x);
21         mr=max(mr,x);
22     }
23     mx=(ml+mr)/2;
24     my=(mu+md)/2;
25     //正方形②的角在正方形①中的情况,分别判断四个角,有一个在里面就成立
26     if(mx>=nl&&mx<=nr&&md>=nd&&md<=nu||mx>=nl&&mx<=nr&&mu>=nd&&mu<=nu||ml>=nl&&ml<=nr&&my>=nd&&my<=nu||mr>=nl&&mr<=nr&&my>=nd&&my<=nu)
27         cout<<"YES"<<endl;
28     //正方形①的角在正方形②中的情况,分别判断四个角,有一个在里面就成立,其中,诸如nu+nr>=ml+my的式子是判断点在直线的上方还是下方
29     else if(nu+nr>=ml+my&&nu<=nr-mx+mu&&nu>=nr-mx+md&&nu+nr<=mr+my||nd+nr>=ml+my&&nd<=nr-mx+mu&&nd>=nr-mx+md&&nd+nr<=mr+my)
30         cout<<"YES"<<endl;
31     else if(nu+nl>=ml+my&&nu<=nl-mx+mu&&nu>=nl-mx+md&&nu+nl<=mr+my||nd+nl>=ml+my&&nd<=nl-mx+mu&&nd>=nl-mx+md&&nd+nl<=mr+my)
32         cout<<"YES"<<endl;
33     //一个正方形中心在另一个中的情况
34     else if(mx>=nl&&mx<=nr&&my>=nd&&my<=nu)
35         cout<<"YES"<<endl;
36     else
37         cout<<"NO"<<endl;
38     return 0;
39 }

 

这种想法不难, 就是有点麻烦。

 

另外在看别人的想法时看到一个比较有意思的解法:

from:https://blog.csdn.net/qq_40858062/article/details/80720092

因为正方形一个是正的,一个成45度角,第二个四边形完全在第一个上下左右就肯定不相交,要看的就是类似图中的情况,其实只要看中间这个小四边形周长和那个45度角四边形上下边界的差的大小关系就好了了,多画几张图可以看出来.....

CodeForces 993A Two Squares(数学 几何)

 

 

 

 

照着他的思路敲了一遍,代码如下:

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 //const double PI=acos(-1);
17 #define Bug cout<<"---------------------"<<endl
18 const int maxn=1e5+10;
19 using namespace std;
20 
21 struct point
22 {
23     int x;
24     int y;
25 };
26 
27 bool cmp(point a,point b)
28 {
29     if(a.x!=b.x)
30         return a.x<b.x;
31     else
32         return a.y<b.y;
33 }
34 
35 int main()
36 {
37     point a[4];
38     point b[4];
39     for(int i=0;i<4;i++)
40         scanf("%d %d",&a[i].x,&a[i].y);    
41     for(int i=0;i<4;i++)
42         scanf("%d %d",&b[i].x,&b[i].y);
43     sort(a,a+4,cmp);
44     sort(b,b+4,cmp);
45     int flag=0;
46     if(b[0].x<=a[3].x&&b[3].x>=a[0].x&&b[1].y<=a[1].y&&b[2].y>=a[0].y)
47     {
48         int p=min(abs(a[0].x-b[3].x),abs(a[3].x-b[0].x));
49         int q=min(fabs(a[0].y-b[2].y),fabs(a[1].y-b[1].y));
50         if((p+q)*2>=b[2].y-b[1].y)
51             flag=1;
52     }
53     if(flag)
54         printf("YES\n");
55     else
56         printf("NO\n");
57     return  0;
58 }

 

上一篇:mybatis-sqlite日期类型对应关系


下一篇:Python中numpy的应用