uva 688 - Mobile Phone Coverage
2024-08-21 13:37:56
经典问题,矩形面积并。
解法:一、矩形分割,每个矩形的两个横坐标和两个纵坐标排序,这样得到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 ;
}
最新文章
- 非交织YUV格式转换
- C/C++之指针加减法
- python学习笔记4(文件操作)
- Nordic Semiconductor nRF52832 蓝牙智能多协议单芯片解决方案荣获《中国电子商情》编辑选择奖
- hadoop的关键进程
- linux下操作
- POJ 1860 Currency Exchange (最短路)
- js函数大全
- GL_INTERFACE
- vi同类品
- mac下安装配置nginx环境
- ZOJ2112--Dynamic Rankings (动态区间第k大)
- JQuery中回车键登陆
- Binding介绍
- 3D Slicer中文教程(七)—图像中值滤波
- Gradle构建Java工程配置详解
- echarts 设置图例的颜色,不设置color,echarts里面也会有默认的颜色
- c# 三种传参方式 in,out,ref
- swift项目初始化并添加忽略文件Swift.ignore
- P2280 [HNOI2003]激光炸弹(二维前缀和)
热门文章
- 禁止ios默认拉动弹性行为
- java中ExecutorService接口
- 转:内核中的内存申请:kmalloc、vmalloc、kzalloc、kcalloc、get_free_pages
- PHP中的常量
- ural 1294 Mars Satellites
- ural 1348 Goat in the Garden 2
- Boost 和 STL 相比有哪些优势和劣势?
- 【android】adb连接几个常见问题(遇到再新增)
- sicily 4379 bicoloring
- 寻访上海西服定制店_Enjoy·雅趣频道_财新网