POJ1151 离散化求矩形面积的并
2024-09-06 12:36:11
/*第一道离散化的题目,虽然是水题,不过还是很高兴。。。*/ #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct rect
{
double x1,x2,y1,y2;
};
#define max 103<<1
rect a[max>>];
double x[max],y[max];
bool flag[max][max];
int n;
double sum; void solve()
{
for(int i=;i<n;i++)
{
for(int j=;j<n<<;j++)
{
if(x[j]>=a[i].x2)
break;
if(x[j]<a[i].x1)
continue;
for(int k=;k<n<<;k++)
{
if(y[k]>=a[i].y2)
break;
if(y[k]<a[i].y1)
continue;
flag[j][k]=true;
}
}
}
for(int i=;i<n<<;i++)
for(int j=;j<n<<;j++)
{
if(flag[i][j])
sum+=(x[i+]-x[i])*(y[j+]-y[j]);
}
} int main()
{
int k=;
while(~scanf("%d",&n)&&n)
{
int cnt=;
for(int i=;i<n;i++)
{
scanf("%lf%lf%lf%lf",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
x[cnt]=a[i].x1;y[cnt]=a[i].y1;cnt++;
x[cnt]=a[i].x2;y[cnt]=a[i].y2;cnt++;
}
sort(x,x+cnt);
sort(y,y+cnt);
sum=;
memset(flag,false,sizeof(flag));
solve();
printf("Test case #%d\n",k++);
printf("Total explored area: %.2lf\n\n",sum);
}
}
最新文章
- 获取终端ip地址
- f4: Facebook’s Warm BLOB Storage System——Erasure Code
- POJ 1469
- Hive的JDBC使用&;并把JDBC放置后台运行
- How to open .ccproj in VS2010?
- Paxos算法(转)
- 搜索与DP:SLIKAR
- 单机使用tungsten 同步mysql数据到mongodb
- ZOJ 3430 Detect the Virus(AC自动机)
- VC生成lib的_stdcall函数名与mingw生成的不一致
- 快速构建Windows 8风格应用3-打包发布应用
- 想成为Java高级工程师的看过来
- 分布式文件系统FastDFS如何做到高可用
- Delphi过程和函数中变量的作用域
- openwrt 域名ping不通 修改dns
- 浅谈 Unix I/O 模型
- 如何优化代码中大量的if/else,switch/case?
- Oracle数据库web维护管理及监控
- How can For each...
- 【剑指offer】数组中出现次数超过数组长度一半的数字,C++实现