Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<cmath>
- #include<algorithm>
- using namespace std;
- struct circle{
- double pos;
- double rad;
- };
- struct square{
- double L;
- double R;
- /* double lenght;
- double width;*/
- };
- double callenght(double r,double w){
- return sqrt((r*r)-(w*w));
- }
- bool Lcmp(square a,square b){
- return a.L < b.L;
- }
- double max(double a,double b){
- return (a > b ? a : b);
- }
- int main()
- {
- int n;
- double l,w;
- scanf("%d %lf %lf",&n,&l,&w);
- circle Carr[n];
- for(int i = 0 ; i < n ; i ++){
- scanf("%lf %lf",&Carr[i].pos,&Carr[i].rad);
- }
- int sn = 0;
- square Sarr[n];
- for(int i = 0 ; i < n ; i ++){
- double pos = Carr[i].pos;
- double rad = Carr[i].rad;
- if(rad*2 + 1 < w)continue;
- double lenght = callenght(2*rad,w);
- // printf("Test converse to square #%d (%.0lf,%.0lf) -> %lf -> [%lf,%lf]\n",i,pos,rad,lenght,pos - lenght/2 , pos + lenght/2);
- Sarr[sn++] = {pos - lenght/2 , pos + lenght/2};
- }
- sort(Sarr,Sarr+sn,Lcmp);
- double maxR = 0;
- double nxtR = -1;
- int ans = 0;
- for(int i = 0 ; i < sn ; ){
- double L = Sarr[i].L;
- double R = Sarr[i].R;
- // printf("#%d : %lf %lf\n",i,L,R);
- if(R < 0)continue;
- if(L > l)break;
- if(L <= maxR){
- nxtR = max(nxtR , R);
- i ++;
- }
- else{
- if(nxtR == -1){
- printf("-1");
- return 0;
- }
- ans++;
- maxR = max(maxR,nxtR);
- // if(maxR > l)break;
- // printf("up to %lf\n",maxR);
- nxtR = -1;
- }
- }
- if(maxR < l && nxtR > maxR){
- maxR = nxtR;
- ans++;
- }
- if(maxR < l){
- printf("-1");
- return 0;
- }
- printf("%d",ans);
- return 0;
- }
- /*
- 3 8 0
- 2 3
- 4 2
- 7 2
- 3 5 0
- 1 1
- 2 1
- 4 1
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement