首页 > 代码库 > 2017ecjtu-summer training #5 UVA10382
2017ecjtu-summer training #5 UVA10382
题意 问最少可用几个圆覆盖矩形区域。
解析 将圆形转换成矩形有效区域,直径小于等于宽度的圆不考虑,从而转化成区间覆盖问题,然后贪心出最少圆。
贪心思想 每次选择出区域左界比上次选出的区域右界小的且区域最长的。更新还未覆盖的区域。
AC 代码
#include<iostream> #include<stdio.h> #include<string.h> #include<cmath> #include<algorithm> #define maxn 10010 using namespace std; struct node { double left; double right; } a[maxn]; bool cmp(node a,node b) { return a.left<b.left; } int n; double l,w; int main() { int i,j,k; while(scanf("%d %lf %lf",&n,&l,&w)!=EOF) { int len=0; double p,r; for(i=0; i<n; i++) { scanf("%lf%lf",&p,&r); if(2*r<=w) continue; double k=sqrt(r*r-w*w/4.0); a[len].right=p+k; a[len].left=p-k; len++; } sort(a,a+len,cmp); int sum=0; double le=0,ri=0; int flag=0; if(a[0].left<=0) { int i=0; while(i<len) { int j=i; while(le>=a[j].left&&j<len) { if(a[j].right>ri) ri=a[j].right; j++; } if(i==j) break; sum++; le=ri; i=j; if(ri>=l) { flag=1; break; } } } if(flag) printf("%d\n",sum); else printf("-1\n"); } return 0; }
2017ecjtu-summer training #5 UVA10382
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。