HDU——2056Rectangles(几何计算)

时间:2022-10-12 07:30:46

Rectangles

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 19243    Accepted Submission(s): 6233

Problem Description
Given two rectangles and the coordinates of two points on the diagonals of each rectangle,you have to calculate the area of the intersected part of two rectangles. its sides are parallel to OX and OY .
 
Input
Input The first line of input is 8 positive numbers which indicate the coordinates of four points that must be on each diagonal.The 8 numbers are x1,y1,x2,y2,x3,y3,x4,y4.That means the two points on the first rectangle are(x1,y1),(x2,y2);the
other two points on the second rectangle are (x3,y3),(x4,y4).
 
Output
Output For each case output the area of their intersected part in a single line.accurate up to 2 decimal places.
 
Sample Input
1.00 1.00 3.00 3.00 2.00 2.00 4.00 4.00
5.00 5.00 13.00 13.00 4.00 4.00 12.50 12.50
 
Sample Output
1.00
56.25

这题首先把给的四个坐标分成两组

每组都要变成主对角线的顺序(即a↗b,c↗d)

可能的顺序共有四种:

1.主对角线,但是a,b顺序反的;

2.为副对角线但a在b左边;

3.为副对角线且a在b右边;

4.主对角线且a在b左边(正确顺序)

然后再总结下面积规律会发现若有重合面积总有

area=【min(b.x,d.x)-max(a.x,c.x)】*【min(d.y,b.y)-max(a.y,c.y)】且此式子也可以判断是否存在重合面积。若出现负数则不重合

代码:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
struct point
{
double x;
double y;
};
inline void change(point &a,point &b)
{
double t;
point tp;
if((a.x<b.x&&a.y>b.y)||(a.x>b.x&&a.y<b.y))//a↘b与b↘a转为主对角线,顺序先不变
{
t=a.y;//这里暂时仅需y交换
a.y=b.y;
b.y=t;
}
if(a.x>b.x&&a.y>b.y)//再将主对角线上的顺序变成↗的顺序
{
tp=a;//整体交换
a=b;
b=tp;
}
}
int main(void)
{
point a,b,c,d;
while (cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y)
{
change(a,b);
change(c,d);
if(min(b.x,d.x)<=max(a.x,c.x)||min(d.y,b.y)<=max(a.y,c.y))//两个多项式均不能为负数(=号包括了边重合)
cout<<"0.00"<<endl;//此题大坑,0也要输出0.00。-.-|||
else
{
double sum=(min(b.x,d.x)-max(a.x,c.x))*(min(d.y,b.y)-max(a.y,c.y));
printf("%.2lf\n",sum);
}
}
return 0;
}