南宁网站建设公司,望野王,家装网站建设,设计师平台网站题干#xff1a;
题目大意#xff1a;
有一块草坪#xff0c;长为l#xff0c;宽为w#xff0c;在它的水平中心线上有n个位置可以安装喷水装置#xff0c;各个位置上的喷水装置的覆盖范围为以它们自己的半径ri为圆。求出最少需要的喷水装置个数#xff0c;如果无论如何…题干
题目大意
有一块草坪长为l宽为w在它的水平中心线上有n个位置可以安装喷水装置各个位置上的喷水装置的覆盖范围为以它们自己的半径ri为圆。求出最少需要的喷水装置个数如果无论如何都不能覆盖就输出-1。
解题报告 这题就是个区间覆盖问题的变形虽然给的是一个个的圆但是我们不难发现求出与上下边的交点这一部分区域才是我们的有效区域然后求个区间覆盖就行了、、、nlogn的算法按说不应该TLE啊但是该优化的都优化了还是TLE看了题解发现有个剪枝但是说实话这个题卡时间没必要吧、、TLE变0ms emmm今天又想了一下好像不是TLE的问题这样会WA吧、、因为本来可能覆盖不到的地方你都变成覆盖得到了、、你求边界那里就不对、、对一个负数去开平方根可能这样会认为是TLE吧、、
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
struct Node {double st,ed;Node(){}Node(double st,double ed):st(st),ed(ed){}bool operator(const Node b) const{if(st ! b.st) return st b.st;return ed b.ed;}
} node[MAX];
int tot,cnt;
int main()
{int n;double l,w,x,r;while(~scanf(%d%lf%lf,n,l,w)) {totcnt0;for(int i 1; in; i) {scanf(%lf %lf,x,r);if(r w/2) continue;//cinxr;//cout x r endl;node[tot] Node(x-sqrt(r*r-w*w/4),xsqrt(r*r-w*w/4));//cout x-sqrt(r*r-w*w/4) endl;}sort(node1,nodetot1);//for(int i 1; itot; i) printf(%f %f\n,node[i].st,node[i].ed);double cure,curs;curscure0;int flag 0;for(int i 1; itot; ) {if(node[i].st curs) {break; }while(itot node[i].stcurs) {if(node[i].ed cure) {cure node[i].ed;}i;}cnt;curs cure;if(curs l) {flag1;break;}}if(flag 0) puts(-1);else printf(%d\n,cnt);}return 0 ;}
还有一个没有排序的算法、这样写就不需要加剪枝了。。但是不知道为什么这样可以。
