c - 请告知我不涉及哪种情况
问题描述
- 给定两个平行于坐标轴的矩形,找到它们所覆盖的区域。
输入格式:输入 的第一行包含 T - 测试用例数。其后是 2T 线。每个测试用例的第一行包含 4 个整数 - xbl、ybl、xtr、ytr - rectangle-1 的左下角和右上角坐标。每个测试用例的第二行包含 4 个整数 - xbl、ybl、xtr、ytr - rectangle-2 的左下角和右上角坐标。
约束
- 1 <= T <= 10000
- -10 6 < x,y <= 10 6
- (xbl, ybl) < (xtr, ytr)
输出格式: 对于每个测试用例,打印 2 个矩形覆盖的区域,用换行符分隔。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
unsigned int recarea(int x1,int y1,int x2,int y2){
int area=0;
area=(x2-x1)*(y2-y1);
return abs(area);
}
unsigned int overarea(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
int top=fmin(y2,y4);
int bottom=fmax(y1,y3);
int left=fmax(x1,x3);
int right=fmin(x2,x4);
int overlaparea=0;
if(bottom<top && left<right){
overlaparea=recarea(left,bottom,right,top);
}
return abs(overlaparea);
}
int main() {
int testcases=0;
scanf("%d",&testcases);
for(int i=0;i<testcases;i++){
int x1,x2,y1,y2,x3,x4,y3,y4;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
scanf("%d %d %d %d",&x3,&y3,&x4,&y4);
int area=recarea(x1,y1,x2,y2)+recarea(x3,y3,x4,y4)-
overarea(x1,y1,x2,y2,x3,y3,x4,y4);
printf("%d\n",area);
}
return 0;
}
变量 x1、y1 是左下坐标,x2、y2 是矩形 1 的右上坐标。变量 x3、y3 是左下坐标,x4、y4 是矩形 2 的右上坐标。
解决方案
请告知我不涉及哪种情况
使用更广泛的数学
area=(x2-x1)*(y2-y1);
给定 -10 6 < x,y <= 10 6容易int
溢出。
最大面积约为 4*10 12,超出了大多数int
实现(32 位或 16 位)的范围。
long long
至少涵盖范围 -(2 63 + 1) ... +(2 63 + 1)
long long recarea(int x1, int y1, int x2, int y2) {
long long area = (0LL + x2 - x1)*(0LL + y2 - y1);
return llabs(area);
}
long long area = recarea(...
printf("%lld\n",area);
也调整overarea()
。
其他
可能存在其他功能问题。示例:int
可能小至 16 位。考虑long
改用处理 -10 6 < x,y <= 10 6。
在旁边
代码使用带有fmin(), fmax()
. 我使用了仅整数方法,而不是在 FP 和整数之间切换时产生各种问题。考虑到较小的范围,这里看起来不错,但不适用于较大的值。
推荐阅读
- java - 从范围列表中查找重叠范围
- ruby-on-rails - `env:Client` SOAP Fault 带有错误字符串`Internal Error (from client)` 在 Savon 2.0 SOAP 请求上具有正确的参数
- .net-core - 当前线程与 Dispatcher 没有关联。触发渲染时使用 InvokeAsync() 将执行切换到 Dispatcher
- css - 我希望我的搜索框保持不透明度:当它处于活动状态时为 100%
- java - 嗨,我创建了一个 javafx 应用程序,其中应将特定图像裁剪为特定大小
- css - 为什么 CSS 样式即使在被覆盖后仍然存在?
- visual-studio - Git Bash:无法打开包含文件:'io.h':Windows 10 上没有这样的文件或目录
- xml - 如何在 VBA 中使用多行字符串变量写入 XML?
- ansible - Ansible 包含 vars 文件
- javascript - RxDb,使用默认索引时无法对字段 XXX 进行排序