const int N = 100; //矩形的最大个数
typedef double typev;
struct seg{
int l, r;
int c; //覆盖数
typev m; //覆盖长度
}segs[N<<3];
struct li{
typev x, ly, hy; //ly为小的,hy为大的
void set(typev x, typev ly, typev hy){
this->x = x, this->ly = ly, this->hy = hy;
}
bool is_l; //标记是否是左边的线段
}lis[N*2];
//左下角是(x1,y1),右上角是(x2,y2), x1<x2,y1<y2的矩形
struct rect{
typev x1, x2, y1, y2;
void read(){
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
}
}rs[N<<1];
typev y[N<<1];
int n, cnt;
bool cmp(li l1, li l2){
return l1.x < l2.x;
}
void build(int id, int l, int r){
segs[id].l = l, segs[id].r = r, segs[id].m = segs[id].c = 0;
if(l < r - 1){
int mid = (l+r)>>1;
build(2*id+1, l, mid);
build(2*id+2, mid, r);
}
}
int binary(int l, int r, typev k){
int mid;
while(l <= r){
mid = (l+r)>>1;
if(y[mid] >= k) r = mid-1;
else l = mid+1;
}
return r+1;
}
void renew(int id){
if(segs[id].c > 0) segs[id].m = y[segs[id].r] - y[segs[id].l];
else if(segs[id].l == segs[id].r - 1) segs[id].m = 0;
else{
segs[id].m = segs[2*id+1].m + segs[2*id+2].m;
}
}
// 可以把insert和del合为一个函数
void modify(int id, int l, int r, int k){
if(segs[id].l >= l && segs[id].r <= r){
segs[id].c += k;
renew(id);
}else if(segs[id].l < segs[id].r - 1){
int mid = (segs[id].l + segs[id].r)>>1;
if(l < mid) modify(2*id+1, l, r, k);
if(r > mid) modify(2*id+2, l, r, k);
renew(id);
}
}
//n个矩形的面积并
typev unionArea(rect* rs, int n){
int i;
typev x1, y1, x2, y2, py1, py2, area;
for(i = 0; i < n; i++){
x1 = rs[i].x1; y1 = rs[i].y1;
x2 = rs[i].x2; y2 = rs[i].y2;
lis[2*i].set(x1, y1, y2);
lis[2*i].is_l = true;
lis[2*i+1].set(x2, y1, y2);
y[2*i] = y1;
y[2*i+1] = y2;
lis[2*i+1].is_l = false;
}
n <<= 1;
sort(y, y + n);
sort(lis, lis+n, cmp);
cnt = unique(y, y + n) - y;
build(0, 0, cnt-1);
area = 0;
for(i = 0; i < n-1; i++){
py1 = binary(0, cnt-1, lis[i].ly);
py2 = binary(0, cnt-1, lis[i].hy);
if(lis[i].is_l) modify(0, py1, py2, 1);
else modify(0, py1, py2, -1);
area += (lis[i+1].x - lis[i].x) * (segs[0].m);
}
return area;
}
分享到:
相关推荐
ACM中对于矩形面积并用线段树+离散化+ 扫描线一类问题求解
在C#编程语言中,计算长方形面积是一个基础的数学操作,主要涉及到变量定义、运算符的使用以及控制台输入输出。在这个简单的程序中,我们将学习如何利用C#实现这个功能,这对于初学者来说是非常好的练习。 首先,...
这里创建了一个`Rectangle`对象`my_rectangle`,长度为5,宽度为4,然后通过调用`get_area`方法计算面积并打印结果。 为了提高代码的可读性和可维护性,我们还可以考虑添加一些验证逻辑,确保长度和宽度都是正数: ...
C++计算矩形面积.。
需要注意的是,矩形面积为`(right - left) * (top - bottom)`,但这里的重叠矩形可能会导致负面积,因此需要进行适当的检查: ```cpp int overlapArea(const Rectangle &rect1, const Rectangle &rect2) { ...
这个程序展示了如何定义一个名为`rect`的类来表示矩形,并提供了计算矩形面积和周长的方法。以下是这个程序的详细解析: 1. **类的定义**: `class rect` 定义了一个名为`rect`的类,用于表示矩形。它包含了四个...
简单C++ 计算矩形面积,只有一个类,和一个方法。
C++计算矩形的面积
学生们需要通过研究和比较,发现长方形面积的规律,并讨论为什么可以用长乘宽来计算面积。 在交流发现部分,学生们分享了自己的发现,让其他同学了解他们的研究结果。通过这种交流,学生们可以学习他人的方法和结果...
在Java中,我们可以创建两个类,分别代表三角形和矩形,并提供相应的计算面积的方法。 1. **创建Rectangle类** 在Java中,我们首先定义一个名为`Rectangle`的类,包含长和宽作为实例变量。然后,我们提供一个`...
这意味着用户可以连续输入多个矩形的长和宽,程序会依次计算并累加这些矩形的面积。循环结构通常使用`for`或`while`语句实现,确保在用户选择停止之前不断重复获取和处理数据。 在处理用户输入时,程序具有部分纠错...
然后调用`getArea()`函数计算矩形的面积,并将结果输出到屏幕上。 ```cpp int main() { Rectangle rect(10, 20, 30, 10); cout () ; return 1; } ``` #### 七、注意事项 1. **坐标系统**:在这个示例中,坐标系...
在本项目中,我们需要使用JavaServer Pages(JSP)技术和Servlet来实现一个简单的Web应用程序,该程序能够接收用户输入的矩形的长度和宽度,计算并显示矩形的周长和面积。首先,我们来看看各个文件的作用。 1. **...
如题,c++实现圆面积,圆周长以及长方形面积,长方形周长的计算。同理,可用于计算三角形等其它图形。
在X轴上水平放置着N个条形图,这N个条形图就组成了一个柱状图,每个条形图都是一个矩形,每个矩形都有相同的宽度,均为1单位长度,但是它们的高度并不相同
用接口设计并实现面积与周长计算 要求:①定义一个接口,其中包含一个计算面积的抽象方法和一个计算周长的抽象方法;②输入数据为圆的半径、三角形...④计算圆、三角形、矩形的面积和周长,并输出原始数据和结算结果。
长方形面积公式的掌握与应用 长方形面积公式是数学中一个重要的概念,它广泛应用于数学、物理、工程等领域。长方形面积公式的掌握对于计算长方形的面积非常重要。本文将详细介绍长方形面积公式的基本概念、应用实例...
- 否则,从栈中弹出栈顶矩形,并计算以弹出矩形为高的最大矩形面积。 - 计算方法:弹出矩形的高度乘以其左右两侧第一个小于它的矩形之间的距离。 - 重复以上步骤,直到栈为空或当前矩形的高度大于等于栈顶矩形的...
9715 相邻最大矩形面积
给定已知的圆的半径,矩形的长和宽,分别求它们的面积和周长