64,649
社区成员
发帖
与我相关
我的任务
分享来个非算法的，求矩形交集的面积
在一个平面坐标系上，有两个矩形，它们的边分别平行于X和Y轴。
其中，矩形A已知， ax1(左边), ax2（右边）, ay1（top的纵坐标）, ay2（bottom纵坐标）. 矩形B，类似，就是 bx1, bx2, by1, by2。这些值都是整数就OK了。
要求是，如果矩形没有交集，返回-1， 有交集，返回交集的面积。
int area(rect const& a, rect const& b)
{
...
}
补齐代码，我认为好的代码应该是简洁的。别用库。你可以写你的辅助函数，宏定义。代码风格也很重要。
其中，矩形A已知， ax1(左边), ax2（右边）, ay1（top的纵坐标）, ay2（bottom纵坐标）. 矩形B，类似，就是 bx1, bx2, by1, by2。这些值都是整数就OK了。
要求是，如果矩形没有交集，返回-1， 有交集，返回交集的面积。
int area(rect const& a, rect const& b)
{
...
}
补齐代码，我认为好的代码应该是简洁的。别用库。你可以写你的辅助函数，宏定义。代码风格也很重要。
...全文
请发表友善的回复…
发表回复
onlyonesai 2012-10-29
- 打赏
- 举报
[Quote=引用 80 楼 的回复:]
菜鸟写了一个，效率不咋的，不过应该易懂哈C/C++ code
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
double ax1,bx1,ax2,bx2,ay1,ay2,by1,by2,s;//ax1(左边), ax2（右边）, ay1（top的纵坐标）, ay2（bottom纵坐标）. 矩形……
[/Quote]
……这个不对吧
菜鸟写了一个，效率不咋的，不过应该易懂哈C/C++ code
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
double ax1,bx1,ax2,bx2,ay1,ay2,by1,by2,s;//ax1(左边), ax2（右边）, ay1（top的纵坐标）, ay2（bottom纵坐标）. 矩形……
[/Quote]
……这个不对吧
zsc09_leaf 2012-10-02
- 打赏
- 举报
这里暂且不考虑精度问题哦。
zsc09_leaf 2012-10-02
- 打赏
- 举报
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)>(b)?(b):(a)
typedef struct rect
{
double left,top,right,bottoom;
}rect;
double area(rect const& a, rect const& b)
{
if(!(b.right > a.left && b.top > a.bottoom && b.left < a.right && b.bottoom < a.top))
{
return 0.00;
}
double h = (MIN(a.top,b.top)) - (MAX(a.bottoom,b.bottoom));
double l = (MIN(a.right,b.right))- (MAX(a.left,b.left));
return h*l;
}zsc09_leaf 2012-10-02
- 打赏
- 举报
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)>(b)?(b):(a)
typedef struct rect
{
double left,top,right,bottoom;
}rect;
double area(rect const& a, rect const& b)
{
if(!(b.right > a.left && b.top > a.bottoom && b.left < a.right && b.bottoom < a.top))
{
return 0.00;
}
double h = (MIN(a.top,b.top)) - (MAX(a.bottoom,b.bottoom));
double l = (MIN(a.right,b.right))- (MAX(a.left,b.left));
return h*l;
}
#define MIN(a,b) (a)>(b)?(b):(a)
typedef struct rect
{
double left,top,right,bottoom;
}rect;
double area(rect const& a, rect const& b)
{
if(!(b.right > a.left && b.top > a.bottoom && b.left < a.right && b.bottoom < a.top))
{
return 0.00;
}
double h = (MIN(a.top,b.top)) - (MAX(a.bottoom,b.bottoom));
double l = (MIN(a.right,b.right))- (MAX(a.left,b.left));
return h*l;
}
hahajluzxb 2012-09-21
- 打赏
- 举报
#include <stdio.h>
#define mintwo(x,y) ((x)>(y)?(y):(x))
#define min(x,y,z,a) mintwo(mintwo(x,y),mintwo(z,a))
main()
{
int ax1,ax2,ay1,ay2,bx1,bx2,by1,by2;
scanf("%d %d %d %d",&ax1,&ax2,&ay1,&ay2);
scanf("%d %d %d %d",&bx1,&bx2,&by1,&by2);
if(!(ax1<ax2&&ay1<ay2)||!(bx1<bx2&&by1<by2))
{
printf("error,one or more rect ");
return;
}
if(ax1>bx2||ax2<bx1||ay1<by2||ay2>by1)
printf("-1\n");
else
printf("%d\n", min(bx2-ax1,ax2-bx1,bx2-bx1,ax2-ax1)*min(ay1-by2,by1-ay2,by2-by1,ay2-ay1));
}
晕，看了一下，发现写错了，重写下吧
#define mintwo(x,y) ((x)>(y)?(y):(x))
#define min(x,y,z,a) mintwo(mintwo(x,y),mintwo(z,a))
main()
{
int ax1,ax2,ay1,ay2,bx1,bx2,by1,by2;
scanf("%d %d %d %d",&ax1,&ax2,&ay1,&ay2);
scanf("%d %d %d %d",&bx1,&bx2,&by1,&by2);
if(!(ax1<ax2&&ay1<ay2)||!(bx1<bx2&&by1<by2))
{
printf("error,one or more rect ");
return;
}
if(ax1>bx2||ax2<bx1||ay1<by2||ay2>by1)
printf("-1\n");
else
printf("%d\n", min(bx2-ax1,ax2-bx1,bx2-bx1,ax2-ax1)*min(ay1-by2,by1-ay2,by2-by1,ay2-ay1));
}
晕，看了一下，发现写错了，重写下吧
windkismet 2012-09-21
- 打赏
- 举报
int area(rect const& a, rect const& b)
{
...
}
ax1\ax2\ay1\ay2\bx1\bx2\by1\by2 根据a\b中的成员替换
就不填函数了，直接给思路，欢迎各位提疑指正：
新的相交矩形定义： 左上角(x1,y1)右下角(x2,y2) 有效矩形，当且仅当 x1<x2 && y1<y2
函数实现如下：
{
x1 = (ax1>bx1)?ax1:bx1;
y1 = (ay1>by1)?ay1:by1;
x2 = (ax2<bx2)?ax2:bx2;
y2 = (ay2<by2)?ay2:by2;
if(x1<x2 && y1<y2)
return ((x2-x1)*(y2-y1));
return -1;
}
{
...
}
ax1\ax2\ay1\ay2\bx1\bx2\by1\by2 根据a\b中的成员替换
就不填函数了，直接给思路，欢迎各位提疑指正：
新的相交矩形定义： 左上角(x1,y1)右下角(x2,y2) 有效矩形，当且仅当 x1<x2 && y1<y2
函数实现如下：
{
x1 = (ax1>bx1)?ax1:bx1;
y1 = (ay1>by1)?ay1:by1;
x2 = (ax2<bx2)?ax2:bx2;
y2 = (ay2<by2)?ay2:by2;
if(x1<x2 && y1<y2)
return ((x2-x1)*(y2-y1));
return -1;
}
hahajluzxb 2012-09-21
- 打赏
- 举报
#include <stdio.h>
main()
{
if(ax1>bx2&&ax2<bx1&&ay1<by2&&ay2>by1)
return -1;
else
return min(|bx2-ax1|,|ax2-bx1|,|bx2-bx1|,|ax2-ax1|)*min(|by2-ay1|,|ay2-by1|,|by2-by1|,|ay2-ay1|);
}
随手写的一个，不知道对不对，望指正，没写全
main()
{
if(ax1>bx2&&ax2<bx1&&ay1<by2&&ay2>by1)
return -1;
else
return min(|bx2-ax1|,|ax2-bx1|,|bx2-bx1|,|ax2-ax1|)*min(|by2-ay1|,|ay2-by1|,|by2-by1|,|ay2-ay1|);
}
随手写的一个，不知道对不对，望指正，没写全
corn8888 2012-09-21
- 打赏
- 举报
汇编都上来了
xcszbdnl 2012-09-20
- 打赏
- 举报
不就是一个线段树的用法么？？
olderma 2012-09-20
- 打赏
- 举报
菜鸟写了一个，效率不咋的，不过应该易懂哈
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
double ax1,bx1,ax2,bx2,ay1,ay2,by1,by2,s;//ax1(左边), ax2（右边）, ay1（top的纵坐标）, ay2（bottom纵坐标）. 矩形B，类似，就是 bx1, bx2, by1, by2
cin>>ax1>>ax2>>bx1>>bx2>>ay1>>ay2>>by1>>by2;
if(((ax1<=bx1)&&(bx1<=ax2))&&((ay2<=by2)&&(by2<=ay1)))
{
s=(ax2-bx1)*(ay1-by2);
cout<<"面积="<<s;
}
else
if(((ax1<=bx1)&&(bx1<=ax2))&&((by2<=ay2)&&(ay2<=by1)))
{
s=(ax2-bx1)*(by1-ay2);
cout<<"面积="<<s;
}
else
{
if(((bx1<=ax1)&&(ax1<=bx2))&&((ay2<=by2)&&(by2<=ay1)))
{
s=(bx2-ax1)*(ay1-by2);
cout<<"面积="<<s;
}
else
{
if(((bx1<=ax1)&&(ax1<=bx2))&&((ay2<=by2)&&(by2<=ay1)))
{
s=(bx2-ax1)*(ay1-by2);
cout<<"面积="<<s;
}
else
{
cout<<"-1";
}
}
}
}niu_a 2012-09-20
- 打赏
- 举报
int longth(int first, int second)
{
return second-first;
}
int min(int first, int second)
{
return first<second?first:second;
}
int max(int first,int second)
{
return first<second?second:first;
}
int area(rect const &a, rect const&b)
{
int w = longth(a.left,a.right)+longth(b.left,b.right)-longth(min(a.left,b.left),max(a.right,b.right));
if(w>0)
{
int h=longth(a.top,a.bottom)+longth(b.top,b.bottom)-longth(min(a.top,b.top),max(a.bottom,b.bottom));
if(h>0)
return w*h；
}
return 0;
}
niu_a 2012-09-20
- 打赏
- 举报
int longth(int first, int second)
{
return second-first;
}
int min(int first, int second)
{
return first<second?first:second;
}
int max(int first,int second)
{
return first<second?second:first;
}
int area(rect const &a, rect const&b)
{
int w = longth(a.left,a.right)+longth(b.left,b.right)-longth(min(a.left,b.left),max(a.right,b.right));
if(w>0)
{
int h=longth(a.top,a.bottom)+longth(b.top,b.bottom)-longth(min(a.top,b.top),max(a.bottom,b.bottom));
if(h>0)
return w*h；
}
return 0;
}
niu_a 2012-09-20
- 打赏
- 举报
int longth(int first, int second)
{
return second-first;
}
int min(int first, int second)
{
return first<second?first:second;
}
int max(int first,int second)
{
return first<second?second:first;
}
int area(rect const &a, rect const&b)
{
int w = longth(a.left,a.right)+longth(b.left,b.right)-longth(min(a.left,b.left),max(a.right,b.right));
if(w>0)
{
int h=longth(a.top,a.bottom)+longth(b.top,b.bottom)-longth(min(a.top,b.top),max(a.bottom,b.bottom));
if(h>0)
return w*h；
}
return 0;
}
{
return second-first;
}
int min(int first, int second)
{
return first<second?first:second;
}
int max(int first,int second)
{
return first<second?second:first;
}
int area(rect const &a, rect const&b)
{
int w = longth(a.left,a.right)+longth(b.left,b.right)-longth(min(a.left,b.left),max(a.right,b.right));
if(w>0)
{
int h=longth(a.top,a.bottom)+longth(b.top,b.bottom)-longth(min(a.top,b.top),max(a.bottom,b.bottom));
if(h>0)
return w*h；
}
return 0;
}
老王爱上猫 2012-09-18
- 打赏
- 举报
当初面试的时候没有弄出来
yuriarthas 2012-09-18
- 打赏
- 举报
怎么楼上这么多代码？不就是看两个矩阵是否有重合的地方么？怎么这么麻烦？还是我想错了？
ri_aje 2012-09-18
- 打赏
- 举报
#include <cstdio>
template <typename T> T const& min (T const& x, T const& y) { return x<y ? x : y; }
template <typename T> T const& max (T const& x, T const& y) { return x>y ? x : y; }
int ax0,ay0,ax1,ay1;
int bx0,by0,bx1,by1;
int area ()
{
int const dx = min(ax1,bx1) - max(ax0,bx0);
int const dy = min(ay1,by1) - max(ay0,by0);
return dx>=0&&dy>=0 ? dx*dy : -1;
}
int main ()
{
int a;
ax0=20;ay0=30;
ax1=80;ay1=70;
bx0=10;by0=50;
bx1=90;by1=60;
a=area();
printf("area=%d\n",a);
return 0;
}
movl ax1, %eax
movl ax0, %edx
cmpl %eax, bx1
cmovle bx1, %eax
cmpl %edx, bx0
cmovge bx0, %edx
movl ay1, %ecx
subl %edx, %eax
movl ay0, %edx
cmpl %ecx, by1
cmovle by1, %ecx
cmpl %edx, by0
cmovge by0, %edx
subl %edx, %ecx
js .L3
testl %eax, %eax
js .L3
imull %ecx, %eax
ret
.L3:
movl $-1, %eax
ret
ruf 2012-09-17
- 打赏
- 举报
bool intersect(const SkIRect& a, const SkIRect& b) {
SkASSERT(&a && &b);
if (!a.isEmpty() && !b.isEmpty() &&
a.fLeft < b.fRight && b.fLeft < a.fRight &&
a.fTop < b.fBottom && b.fTop < a.fBottom) {
fLeft = SkMax32(a.fLeft, b.fLeft);
fTop = SkMax32(a.fTop, b.fTop);
fRight = SkMin32(a.fRight, b.fRight);
fBottom = SkMin32(a.fBottom, b.fBottom);
return true;
}
return false;
}
SkASSERT(&a && &b);
if (!a.isEmpty() && !b.isEmpty() &&
a.fLeft < b.fRight && b.fLeft < a.fRight &&
a.fTop < b.fBottom && b.fTop < a.fBottom) {
fLeft = SkMax32(a.fLeft, b.fLeft);
fTop = SkMax32(a.fTop, b.fTop);
fRight = SkMin32(a.fRight, b.fRight);
fBottom = SkMin32(a.fBottom, b.fBottom);
return true;
}
return false;
}
赵4老师 2012-09-17
- 打赏
- 举报
编译运行通过的版本：
#include <stdio.h>
int ax1,ay1,ax2,ay2;
int bx1,by1,bx2,by2;
//在一个平面坐标系上，有两个矩形，它们的边分别平行于X和Y轴。
//其中，矩形A已知， ax1(左边), ax2（右边）, ay1（top的纵坐标）, ay2（bottom纵坐标）. 矩形B，类似，就是 bx1, bx2, by1, by2。这些值都是整数就OK了。
//要求是，如果矩形没有交集，返回-1， 有交集，返回交集的面积。
int area() {
int b1c=0,b2c=0;
//__asm int 3;//快速定位Release版汇编代码用
if (bx1<ax1) b1c+=3*0;
else if (ax2<=bx1) b1c+=3*2;
else b1c+=3*1;
if (by1<ay1) b1c+= 0;
else if (ay2<=by1) b1c+= 2;
else b1c+= 1;
if (bx2<ax1) b2c+=3*0;
else if (ax2<=bx2) b2c+=3*2;
else b2c+=3*1;
if (by2<ay1) b2c+= 0;
else if (ay2<=by2) b2c+= 2;
else b2c+= 1;
switch (b1c*9+b2c) {
case 0:
case 1:
case 2:
case 3:
case 6:
case 10:
case 11:
case 20:
case 23:
case 26:
case 30:
case 33:
case 50:
case 53:
case 60:
case 61:
case 62:
case 70:
case 71:
case 80:
return -1;
case 4:
return (bx2-ax1)*(by2-ay1);
case 5:
return (bx2-ax1)*(ay2-ay1);
case 7:
return (ax2-ax1)*(by2-ay1);
case 8:
return (ax2-ax1)*(ay2-ay1);
case 13:
return (bx2-ax1)*(by2-by1);
case 14:
return (bx2-ax1)*(ay2-by1);
case 16:
return (ax2-ax1)*(by2-by1);
case 17:
return (ax2-ax1)*(ay2-by1);
case 31:
return (bx2-bx1)*(by2-ay1);
case 32:
return (bx2-bx1)*(ay2-ay1);
case 34:
return (ax2-bx1)*(by2-ay1);
case 35:
return (ax2-bx1)*(ay2-ay1);
case 40:
return (bx2-bx1)*(by2-by1);
case 41:
return (bx2-bx1)*(ay2-by1);
case 43:
return (ax2-bx1)*(by2-by1);
case 44:
return (ax2-bx1)*(ay2-by1);
case 9:
case 12:
case 15:
case 18:
case 19:
case 21:
case 22:
case 24:
case 25:
case 27:
case 28:
case 29:
case 36:
case 37:
case 38:
case 39:
case 42:
case 45:
case 46:
case 47:
case 48:
case 49:
case 51:
case 52:
case 54:
case 55:
case 56:
case 57:
case 58:
case 59:
case 63:
case 64:
case 65:
case 66:
case 67:
case 68:
case 69:
case 72:
case 73:
case 74:
case 75:
case 76:
case 77:
case 78:
case 79:
printf("not ax1<=ax2 or not ay1<ay2 or not bx1<bx2 or not by1<by2!");
return -1;
break;
}
return -1;
}
int main() {
int a;
ax1=20;ay1=30;
ax2=80;ay2=70;
bx1=10;by1=50;
bx2=90;by2=60;
a=area();
printf("area=%d\n",a);
}
//area=600
赵4老师 2012-09-17
- 打赏
- 举报
68楼中指令
004010A7 FF 24 9D 40 12 40 00 jmp dword ptr [ebx*4+401240h]
使用的跳转表：
004010A7 FF 24 9D 40 12 40 00 jmp dword ptr [ebx*4+401240h]
使用的跳转表：
00401240 00401234 004010AE 004010CA
0040124C 004010D1 004010ED 00401226
00401258 004010F4 00401110 0040112F
00401264 0040114B 0040116A 00401180
00401270 00401199 004011AF 004011C8
0040127C 004011DE 004011F7 0040120D
xiao910xx 2012-09-17
- 打赏
- 举报
选两个矩形的左上角的坐标 可判断出上下和左右的位置关系
然后可选择 一个的左上的坐标 一个选择右下的坐标 可得到是否重叠或重叠矩形的边长
然后可选择 一个的左上的坐标 一个选择右下的坐标 可得到是否重叠或重叠矩形的边长
加载更多回复（65）
