Codeforces 993A. Two Squares(暴力求解)
2024-10-20 07:46:53
解题思路（暴力解法）
- 平行于x轴的正方形和与x轴成45度倾斜的正方形相交的点中必定有整数点。即若两正方形相交，必定存在整数i,j，使（i,j）同时属于两个正方形。
- 我们把两个正方形中的整数点都找出来，看一下有没有重复点，就可以判断是否相交。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point{
int x;int y;
}sq[4],sp[4];
bool cmp(point a,point b){
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
//t[i][j]=1表示第一个正方形包含这个点。
int t[220][220];
void tian(point a,point b){
for(int i = a.x;i <= b.x; ++i){
for(int j = a.y;j <= b.y; ++j){
t[i][j] = 1;
}
}
}
//判断第二个正方形是否包含t[i][j]为1的点(i,j)
bool judge(point* sp){
for(int i = sp[0].x;i <= sp[1].x; ++i){
for(int j = 0;j <= i-sp[0].x; ++j){
if(t[i][sp[0].y+j] == 1 or t[i][sp[0].y-j] == 1){
return true;
}
}
}
for(int i = sp[1].x;i <= sp[3].x; ++i){
for(int j = 0;j <= sp[2].y-sp[0].y-(i-sp[1].x); ++j){
if(t[i][sp[0].y+j] == 1 or t[i][sp[0].y-j] == 1){
return true;
}
}
}
return false;
}
int main(){
for(int i = 0;i < 4; ++i) cin >> sq[i].x >> sq[i].y, sq[i].x+=100,sq[i].y+=100;
for(int i = 0;i < 4; ++i) cin >> sp[i].x >> sp[i].y, sp[i].x+=100,sp[i].y+=100;
sort(sq,sq+4,cmp);
sort(sp,sp+4,cmp);
tian(sq[0],sq[3]);
if(judge(sp)) cout << "YES" << endl;
else cout << "NO" << endl;
return 0;
}
最新文章
- SELENIUM2 使用JavascriptExecutor在页面Javascipt执行
- Strategy策略模式
- idHTTP访问百度
- Wpf自定义路由事件
- Twenty Newsgroups Classification实例任务之TrainNaiveBayesJob(一)
- 算法系列——huffman编码
- Windows安装TensorFlow
- vivo4.0系统怎么不ROOT激活Xposed框架的教程
- asp.net core 今日所得
- Windows下搭建Python虚拟环境
- jquery|js|jq常用正则
- 学习CSS布局 - max-width
- supervisor-program配置
- JAVA中使用Apache HttpComponents Client的进行GET/POST请求使用案例
- jquery带token访问接口ajax
- js中replace()方法
- 1711 Number Sequence（kmp）
- PAT 甲级 1032 Sharing
- iPhoneX页面安全区域与内容重叠问题
- linux系统下单节点hadoop2的配置