CodeForces 993A Two Squares（数学几何）

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

题意：

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

思路：

刚开始的想法：

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

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

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

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

代码如下：

 #include "iostream"

 #include "algorithm"

 using namespace std;

 int main()

 {

     double nu,nd,nl,nr,mu,md,ml,mr,mx,my,x,y;//u,d,l,r，分别记录最上，最下，最左，最右的值，mx，my记录的是正方形②中心的坐标

     nu=nr=mu=mr=-;//由于范围是-100~100，所以赋初值

     nd=nl=md=ml=;

     for(int i=;i<;i++){

         cin>>x>>y;

         nd=min(nd,y);

         nu=max(nu,y);

         nl=min(nl,x);

         nr=max(nr,x);

     }

     for(int i=;i<;i++){

         cin>>x>>y;

         md=min(md,y);

         mu=max(mu,y);

         ml=min(ml,x);

         mr=max(mr,x);

     }

     mx=(ml+mr)/;

     my=(mu+md)/;

     //正方形②的角在正方形①中的情况，分别判断四个角，有一个在里面就成立

     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)

         cout<<"YES"<<endl;

     //正方形①的角在正方形②中的情况，分别判断四个角，有一个在里面就成立，其中，诸如nu+nr>=ml+my的式子是判断点在直线的上方还是下方

     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)

         cout<<"YES"<<endl;

     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)

         cout<<"YES"<<endl;

     //一个正方形中心在另一个中的情况

     else if(mx>=nl&&mx<=nr&&my>=nd&&my<=nu)

         cout<<"YES"<<endl;

     else

         cout<<"NO"<<endl;

     return ;

 }

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

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

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

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

照着他的思路敲了一遍，代码如下：

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <math.h>

 #include <algorithm>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <sstream>

 const int INF=0x3f3f3f3f;

 typedef long long LL;

 const int mod=1e9+;

 //const double PI=acos(-1);

 #define Bug cout<<"---------------------"<<endl

 const int maxn=1e5+;

 using namespace std;

 struct point

 {

     int x;

     int y;

 };

 bool cmp(point a,point b)

 {

     if(a.x!=b.x)

         return a.x<b.x;

     else

         return a.y<b.y;

 }

 int main()

 {

     point a[];

     point b[];

     for(int i=;i<;i++)

         scanf("%d %d",&a[i].x,&a[i].y);

     for(int i=;i<;i++)

         scanf("%d %d",&b[i].x,&b[i].y);

     sort(a,a+,cmp);

     sort(b,b+,cmp);

     int flag=;

     if(b[].x<=a[].x&&b[].x>=a[].x&&b[].y<=a[].y&&b[].y>=a[].y)

     {

         int p=min(abs(a[].x-b[].x),abs(a[].x-b[].x));

         int q=min(fabs(a[].y-b[].y),fabs(a[].y-b[].y));

         if((p+q)*>=b[].y-b[].y)

             flag=;

     }

     if(flag)

         printf("YES\n");

     else

         printf("NO\n");

     return  ;

 }

巴特西

CodeForces 993A Two Squares（数学几何）

最新文章

热门文章

巴特西

CodeForces 993A Two Squares（数学 几何）

最新文章

热门文章

CodeForces 993A Two Squares（数学几何）