经典问题,矩形面积并。
解法:一、矩形分割,每个矩形的两个横坐标和两个纵坐标排序,这样得到2n*2n个区间,对这些区间依次判断是否包含在n个矩形中间即可。
      二、扫描线。具体还没实现过。
 #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std; int main()
{
int n, i, j, k, cases;
double area, x[], y[], r[], dx[*], dy[*];
cases = ;
while(cin>>n && n)
{
for(i=; i<n; i++)
{
cin >> x[i] >> y[i] >> r[i];
dx[i*] = x[i] - r[i], dx[i*+] = x[i] + r[i];
dy[i*] = y[i] - r[i], dy[i*+] = y[i] + r[i];
}
sort(dx, dx+*n);
sort(dy, dy+*n);
area = 0.0;
for(i = ; i < *n; i++)
for(j = ; j < *n; j++)
for(k = ; k < n; k++)
{
if(dx[i-]>=x[k]-r[k] && dx[i]<=x[k]+r[k])
if(dy[j-]>=y[k]-r[k] && dy[j]<=y[k]+r[k])
{
area += (dx[i] - dx[i-]) * (dy[j] - dy[j-]);
break;
}
}
printf("%d %.2lf\n", ++cases, area);
}
return ;
}

最新文章

  1. 非交织YUV格式转换
  2. C/C++之指针加减法
  3. python学习笔记4(文件操作)
  4. Nordic Semiconductor nRF52832 蓝牙智能多协议单芯片解决方案荣获《中国电子商情》编辑选择奖
  5. hadoop的关键进程
  6. linux下操作
  7. POJ 1860 Currency Exchange (最短路)
  8. js函数大全
  9. GL_INTERFACE
  10. vi同类品
  11. mac下安装配置nginx环境
  12. ZOJ2112--Dynamic Rankings (动态区间第k大)
  13. JQuery中回车键登陆
  14. Binding介绍
  15. 3D Slicer中文教程(七)—图像中值滤波
  16. Gradle构建Java工程配置详解
  17. echarts 设置图例的颜色,不设置color,echarts里面也会有默认的颜色
  18. c# 三种传参方式 in,out,ref
  19. swift项目初始化并添加忽略文件Swift.ignore
  20. P2280 [HNOI2003]激光炸弹(二维前缀和)

热门文章

  1. 禁止ios默认拉动弹性行为
  2. java中ExecutorService接口
  3. 转:内核中的内存申请:kmalloc、vmalloc、kzalloc、kcalloc、get_free_pages
  4. PHP中的常量
  5. ural 1294 Mars Satellites
  6. ural 1348 Goat in the Garden 2
  7. Boost 和 STL 相比有哪些优势和劣势?
  8. 【android】adb连接几个常见问题(遇到再新增)
  9. sicily 4379 bicoloring
  10. 寻访上海西服定制店_Enjoy·雅趣频道_财新网