codeforce 994c 思维题

http://codeforces.com/problemset/problem/994/C

给你两个正方形 的四个顶点，让你求是否两者有交点

用set来维护所有在正方形里面的点，这样看两个set里面是否有相同的点，如果有不就是相交了 

#include
using namespace std;
const int mod =1e9+7;
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<=b;i++)
struct node
{int x,y;
}num1[10],num2[10];
bool cmpx(node a,node b)
{return a.x >a,b;
int main()
{rep(i,1,4)cin>>num1[i].x>>num1[i].y;rep(i,1,4)cin>>num2[i].x>>num2[i].y;sort(num1+1,num1+1+4,cmpx);int mi1=num1[1].x;int mx1=num1[4].x;sort(num1+1,num1+1+4,cmpy);rep(i,mi1,mx1)rep(j,num1[1].y,num1[4].y)a.insert(make_pair(i,j));sort(num2+1,num2+1+4,cmpx);int mi2=num2[1].x;int mx2=num2[4].x;int mid=(mx2+mi2)/2;    sort(num2+1,num2+1+4,cmpy);rep(i,0,mx2-mid){rep(j,num2[1].y,num2[4].y)b.insert(make_pair(mid+i,j)),b.insert(make_pair(mid-i,j));num2[1].y++;num2[4].y--;//因为第二个正方形是倾斜的，所以枚举点的时候是从对角线上开始，向两边枚举}bool flag = false;for (auto i: a){for (auto j: b){if (i == j) { flag = true; break; }}if (flag) break;}if(flag==1)cout<<"YES"<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！