Water spray ( Two )

The time limit :3000 ms  |  Memory limit :65535 KB
difficulty :4
 
describe
There's a lawn , Transverse length w, The longitudinal length is h, It is installed at different positions on its transverse center line n(n<=10000) A dot sprinkler , Every sprinkler i The effect of spraying water is to make it center with a radius of Ri All the circles are wetted . Please choose as few sprinklers as possible from the ones given , Wet the whole lawn .
 
Input
Enter a positive integer in the first line N Expressing common ownership n Test data .
The first line of each set of test data has three integers n,w,h,n Expressing common ownership n A sprinkler ,w Indicates the transverse length of the lawn ,h Represents the longitudinal length of the lawn .
And then n That's ok , Both have two integers xi and ri,xi It means the first one i The abscissa of a sprinkler ( On the far left is 0),ri Represents the radius of the circle that the sprinkler can cover .
Output
Each group of test data output a positive integer , Indicates how many sprinklers are needed , Each output occupies a separate line .
If there's no way to wet the whole lawn , Please export 0.
The sample input
2
2 8 6
1 1
4 5
2 10 6
4 5
6 5
Explain : It belongs to the greedy optimal solution problem
Code
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct T
{
int a,b;
}c[];
int cmp(T n,T m)
{
if(n.a<m.a)
return ;
if(n.a==m.a && n.b>m.b)
return ;
return ;
}
int main()
{
int i,m,n,k=;
int w,h,x,r;
scanf("%d",&m);
while(m--)
{int k=; int max=-;
scanf("%d %d %d",&n,&w,&h);
for(i=;i<n;i++)
{
scanf("%d %d",&x,&r);
if(*r>h)// Get rid of the ones that don't meet the conditions ,
{
c[k].a=x-sqrt(r*r-h*h/);
if(c[k].a<)
c[k].a=;
c[k].b=sqrt(r*r-h*h/)+x;
if(c[k].b>w)
c[k].b=w;
if(c[k].b>max)
max=c[k].b;
k++;// Recalculate the number of groups in the array
}
} sort(c,c+k,cmp);// Quick line up , Prevent overtime
if(c[].a!= || max!=w)
printf("0\n");
else
{ int count=;
int f=;
int start=,last=;
while(start!=w)
{
for(i=f; i<k; i++)
if(c[i].a<=start && c[i].b>last)
{
last=c[i].b;
f=i+;
}
if(last==start)// There is no solution to this situation
{
count=;
break;
}
start=last;// Redefine the boundary
count++;
}
cout<<count<<endl;
}
}
return ;
}

ny12 Water spray ( Two ) More articles about

  1. nyoj 12—— Sprinkler two ——————【 greedy - Interval coverage 】

    Water spray ( Two ) The time limit :3000 ms  |  Memory limit :65535 KB difficulty :4   describe There's a lawn , Transverse length w, The longitudinal length is h, It is installed at different positions on its transverse center line n(n<=10000) It's a dot ...

  2. ACM Water spray ( Two )

    Water spray ( Two ) The time limit :3000 ms  |  Memory limit :65535 KB difficulty :4   describe There's a lawn , Transverse length w, The longitudinal length is h, It is installed at different positions on its transverse center line n(n<=10000) It's a dot ...

  3. Several kinds of interval covering problems based on greedy algorithm nyoj 12 Water spray ( Two ) nyoj 14 The arrangement of the venue

    1) Interval complete covering problem Problem description : Given a length of m The range of , Give more n The start and end of a line segment ( Notice that this is a closed interval ), Find the minimum number of line segments to cover the entire interval Examples : Interval length 8, Optional overlay line segments [2,6],[1, ...

  4. NYOJ 12 Water spray ( Two )

    pid=12"> Water spray ( Two ) The time limit :3000 ms  |  Memory limit :65535 KB difficulty :4 Description and narration There's a lawn , Transverse length w, The longitudinal length is h, It is installed at different positions on its transverse center line n( ...

  5. NYOJ 12: Water spray ( Two )( greedy , Interval covering problem )

    12- Water spray ( Two ) Memory limit :64MB  The time limit :3000ms  Special judgement : No Passing number :28  Submission number :109  difficulty :4 Title Description : There's a lawn , Transverse length w, The longitudinal length is h, It is installed at different positions on its transverse center line n ...

  6. The problem of greed : Interval coverage NYOJ Water spray ( Two )

    Water spray ( Two ) The time limit :3000 ms  |  Memory limit :65535 KB difficulty :4 describe There's a lawn , Transverse length w, The longitudinal length is h, It is installed at different positions on its transverse center line n(n<=10000) A little bit of water spray ...

  7. nyoj subject 12 Water spray ( Two )

    Water spray ( Two ) The time limit :3000 ms  |  Memory limit :65535 KB difficulty :4   describe There's a lawn , Transverse length w, The longitudinal length is h, It is installed at different positions on its transverse center line n(n<=10000) It's a dot ...

  8. NYOJ subject 12 Water spray ( Two )

    #include<iostream> #include<algorithm> #include<cmath> using namespace std; struct ...

  9. NYOJ Water spray ( Two )

    The title changes to , The length range covered by each faucet in the abscissa direction , The problem after the conversion is a bit like the problem of venue arrangement , And then the next option is based on greed , We're going to sort these intervals , Sort from small to large according to the left end of the interval , Then select from left to right , The condition is when ...

Random recommendation

  1. iOS APP How to be safe

    Originally Write an article <iOS How to be safe -- Reverse engineering - Reveal.IDA.Hopper.https Grab the bag etc. >, I found that the article was a bit miscellaneous , also “iOS How to be safe ” This part is more and more , Think Divide it out ...

  2. WCF-- Safety tips ...

    because WCF The service of writing needs Ajax To make the call ( This configuration process is also quite a process ~~(╯﹏╰)b The experience of ...), So the calling process can be seen by the foreground , No more security measures , It's really like a naked interface on the Internet ... Anyway ...

  3. thinkphp Paging search criteria with Chinese parameters

    /** * Chinese processing * @param type $str * @return str * $author lxh */ function url2word($str){ $sub=strpos($s ...

  4. netaddr 0.7.12

    Pythonic manipulation of IPv4, IPv6, CIDR, EUI and MAC network addresses https://pypi.python.org/pyp ...

  5. java The QR code uses Google's zxing Generate qr code , Analysis of QR code

    Generate qr code @RequestMapping("/123") public void test(HttpServletRequest request,HttpServletRespo ...

  6. 12 It's amazing for programmers CSS3 Effect Library

    Abreast of the times CSS3 All equipped with new features , To design and create animated and interactive web pages . In this paper , You can find some very good CSS3 Effect Library , Let's get you started Web The design looks more compelling . What are you waiting for ? Let's look at it together ! Animate.cs ...

  7. HDU 5904 LCIS

    $dp$. The breakthrough of this problem lies in the requirement that the number is continuous . The longest rising length of two strings ending with a number can be recorded respectively , Then enumerate which number ends to get the answer . because $case$ A little bit more , Not every time $memset$, additional ...

  8. RFM Models and R Language implementation

    I always think that climbing mountains is small , can . Every time I come to the starting point , Daniel , Come slowly and share with me ,please~ --------------------------- One . Basic concepts According to the Database Marketing Institute of the United States Arth ...

  9. android Debugging skills of development

    We all know ,android After the breakpoint of debugging, the runtime should use debug as->android application But it's very inefficient , So do we have a quick way ? Of course. . We're done with breakpoints ...

  10. 【 turn 】pymongo Implement fuzzy query

    pymongo Fuzzy matching query in mongo In this way {'asr':/ takki /} Use pymongo Two ways of implementation 1.import re {'asr':re.compile(' takki ')} 2.{'asr ...