噴水装置(二)

5031 ワード
C++
噴水装置(二)
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
4
説明
横方向の長さw、縦方向の長さhの芝生があり、その横中心線上の異なる位置にn(n<=10000)個の点状の噴水装置が装着されており、各噴水装置iの噴水効果は、それを中心とした半径Riの円を濡らすことである.与えられた噴水装置の中からできるだけ少ない噴水装置を選択し、芝生全体を濡らしてください.
入力
1行目に正の整数Nを入力すると、n回のテストデータが共有されます.
各試験データの最初の行には、3つの整数n,w,h,nがn個の噴水装置を表し、wが芝生の横方向の長さを表し、hが芝生の縦方向の長さを表す.
その後のn行には、いずれも2つの整数xiとriがあり、xiはi番目の噴水装置の横座標(左端が0)を表し、riはこの噴水装置が覆うことができる円の半径を表す.
しゅつりょく
各試験データのセットは正の整数を出力し、合計何個の噴水装置が必要かを示し、各出力は単独で1行を占めている.
芝生全体を湿らせる案がない場合は、0を出力してください.
サンプル入力
2
2 8 6
1 1
4 5
2 10 6
4 5
6 5

サンプル出力
1
2
 
    
    ：
#include<iostream>
#include<cstdlib>
#include<cmath>
#include <algorithm>
using namespace std;
struct S 
{
	double a;
	double b;
}t[1000000];
int cmp(const S& c,const S& d)
{
	return c.a==d.a&&c.b>d.b||c.a<d.a;
}
int main()
{
	int N,n,w,h,i,k;
	double x,y,end,temp,max1=0;
	cin >> N;
	while (N--)
	{
		k=0;
		cin >> n >> w >> h;
		while(n--)
		{
			cin >> x >> y;
			int d=(int)sqrt(y*y-(h/2.0)*(h/2.0));
			if (y>h/2.0&&x+d>=0&&x-d<=w)
			{
				t[k].a=x-d;
				t[k++].b=x+d;
			}
		}
		sort(t,t+k,cmp);
		i=0;
		int cnt=0;
		end=t[0].a;
		while (end<=w&&i<k)
		{
			temp=end;
			while (t[i].a<=end&&i<k)
			{
				if (temp<t[i].b)
				{
					max1=t[i].b;
					temp=t[i].b;
				}
				i++;
			}
			end=temp+1;
			cnt++;
		}
		if (t[0].a>0||max1<w)
		{
			cout << 0 << endl;
			continue;
		}
		cout << cnt << endl;
	}
	return 0;
}
 


  コード:


  
#include <stdio.h>
#include <math.h>
#include <algorithm>
using std::sort;
struct node{
	double le, ri;
}s[1005];
int cmp(node a, node b)
{
	return a.le < b.le;
}
int main()
{
	int n, t;
	double w, h;
	scanf("%d", &t);
	while(t --){
		scanf("%d%lf%lf", &n, &w, &h);
		h /= 2;  //   2
		int i, j;
		double temp, r;
		for(i = 0, j = 0; i < n; i ++){
			scanf("%lf%lf", &temp, &r);
			if(r <= h) continue;//    ，             
			else{
				double temp1 = sqrt(r*r-h*h);//            
				s[j].le = temp -temp1;//   
				s[j++].ri = temp+temp1;//   
			}
		}
		sort(s, s+j, cmp);//  
	//	for(i = 0; i < j; i ++){
	//		printf("%lf %lf..
", s[i].le, s[i].ri);
	//	}
		if(s[0].le > 0) {printf("0
"); continue;} //        0，   0   ，    0
		double end = 0;
		i = 0;
		int cou = 0;
		while(end <= w&&i < j&&cou <= n){//           
			temp = end;
			while(s[i].le <= end&&i <j ){
				if(s[i].ri > temp) temp = s[i].ri;
				i++;
			}
			end = temp+0.000001;//      0.00001，      ，    
			++cou;
		}
		if(end < w||cou > n){//  cou>n       ， end<w      w
			printf("0
");
		}
		else{ 
			printf("%d
", cou);
		}
	}
	return 0;
} 
  

  ：
  
 
    
 
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
double r,x,y,width,height;
class Circle
{
public:
	Circle(double x,double r):x(x),r(r){}
	double Left() const{
		if(r*r-height*height/4<0) return x;return x-sqrt(r*r-(height*height/4));}
	double Right() const{if(r*r-height*height/4<0) return x;return x+sqrt(r*r-(height*height/4));}
	friend ostream & operator<<(ostream& out,const Circle& circle);
private:
	double x,r;
};
ostream & operator<<(ostream& out,const Circle& circle)
{
	out<<circle.x<<" "<<circle.r;
	return out;
}
struct CircleLess
{
	bool operator()(const Circle& c1,const Circle& c2)
	{
		return c1.Right()<c2.Right();
	}
};

int main()
{

	int m;
	cin>>m;
	while(m--)
	{
		int n;
		
		vector<Circle> Rs;
		cin>>n>>width>>height;
		Rs.reserve(n);
		
		
		while(n--)
		{
			cin>>x>>r;
			Rs.push_back(Circle(x,r));
		}
		sort(Rs.begin(),Rs.end(),CircleLess());
		vector<int> choosed;
		choosed.push_back(-1);
		double len=0;
		try{
			while(len<width)
			{
				int last=-1;
				for(vector<Circle>::size_type i=choosed.back()+1;i!=Rs.size();i++)
				{
					if (Rs[i].Left()<=len)
					{
						//cout<<Rs[i].Left()<<endl;
						last=i;
					}
				}
				if (last==-1) throw -1;
				else
				{
					choosed.push_back(last);
					len=Rs[last].Right();
				}
			}	
			cout<<choosed.size()-1<<endl;
		
		}catch(...)
		{
			cout<<0<<endl;
		}
	}

}
Docker公式イメージのmysqlの文字コードを変更する方法
Docker上のRailsのActiveStorageでActiveStorage::IntegrityErrorが出る