C. Two Squares

题目链接

Codeforces Round #488 by NEAR (Div. 2)--C. Two Squares

题解

简单题。题意大概是给定两个正方形,一个边平行于坐标轴,另一个边与坐标轴成45度。求这两个正方形有无公共部分(一个点也算)。
因为数据规模并不大,判断某一正方形中的每一点有没有出现在另一正方形即可。

代码

#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
int q1, q2, q3, q4, q5, q6, q7, q8;
pair<int,int> w[5],u,d,l,r;

int main() {
    cin >> q1 >> q2 >> q3 >> q4 >> q5 >> q6 >> q7 >> q8;
    cin >> w[1].first >> w[1].second >> w[2].first >> w[2].second >> w[3].first >> w[3].second >> w[4].first >> w[4].second;
    sort(w + 1, w + 5);
    l = w[1];
    r = w[4];
    u = w[2].second > w[3].second ? w[2] : w[3];
    d = w[2].second < w[3].second ? w[2] : w[3];
    bool ans=false;
    for (int x = min(min(q1, q3), min(q5, q7)); x <= max(max(q1, q3), max(q5, q7)); x++) {
        for (int y = min(min(q2, q4), min(q6, q8)); y <= max(max(q2, q4), max(q6, q8)); y++) {
            if (x <= u.first) {
                if (y <= l.second + x - l.first&&y >= l.second - x + l.first)ans = true;
            }
            else {
                if (y <= r.second - x + r.first&&y >= r.second + x -r.first)ans = true;
            }
        }
    }
    if (ans) cout << "YES";
    else cout << "NO";
}

标签: implementation, geometry

添加新评论