fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <complex>
  5. using namespace std;
  6.  
  7. static const double EPS = 1e-9;
  8. static const double PI = acos(-1);
  9. static const double WEAK_EPS = 1e-7;
  10.  
  11. typedef complex<double> P;
  12. struct L : public vector<P> {L(const P &a, const P &b) {push_back(a); push_back(b);} };
  13. struct C {P p; double r;C(const P &p, double r) : p(p), r(r) { } C(){} };
  14.  
  15.  
  16. vector<P> C_cp(C a,C b){
  17. 	vector<P> ret;
  18. 	double L = abs(a.p-b.p);
  19.  
  20. 	if(	L-a.r-b.r > EPS || (abs(a.p-b.p)<EPS && fabs(a.r-b.r)<EPS) || 
  21. 		abs(a.p-b.p) < abs(a.r-b.r)
  22. 	)return ret;
  23.  
  24. 	double theta = atan2(b.p.imag()-a.p.imag(),b.p.real()-a.p.real());
  25. 	double c = (L*L+a.r*a.r-b.r*b.r)/(2*L*a.r);
  26. 	ret.push_back(
  27. 		P(a.p.real()+a.r*cos(theta+acos(c)),
  28. 		  a.p.imag()+a.r*sin(theta+acos(c)))
  29. 	);
  30. 	if(fabs(L-a.r-b.r) > EPS)
  31. 		ret.push_back(
  32. 			P(a.p.real()+a.r*cos(theta-acos(c)),
  33. 			  a.p.imag()+a.r*sin(theta-acos(c)))
  34. 		);
  35. 	return ret;
  36. }
  37.  
  38.  
  39. P getPedal(L l, P p){
  40. 	double A;
  41. 	if(abs(l[1].real()-l[0].real()) < EPS){
  42. 		return P(l[1].real(),p.imag()); // important
  43. 	}else{
  44. 		A = (l[1].imag()-l[0].imag())/(l[1].real()-l[0].real());
  45. 	}
  46. 	double a = -A , b = 1 , c = A*l[0].real() - l[0].imag();
  47. 	double t = (a*p.real() + b*p.imag() + c)/(a*a+b*b);
  48. 	return p-t * P(a,b);
  49. }
  50.  
  51. vector<P> crosspointCL(const L l, const C c){
  52. 	vector<P> ret;
  53. 	P p = getPedal(l,c.p);
  54. 	if(	abs(p-c.p) > c.r+EPS)return ret;
  55. 	P e = P((l[1]-l[0])/abs(l[1]-l[0]));
  56. 	double S = sqrt(c.r*c.r-abs(p-c.p)*abs(p-c.p));
  57. 	ret.push_back(p+S*e);
  58. 	ret.push_back(p-S*e);
  59. 	return ret;
  60. }
  61.  
  62. P memo[720];
  63.  
  64.  
  65.  
  66. bool check(const int &N,const int &W,const int &H,const vector<P> &p,const double &R){
  67. 	P vertex[4] = {P(0,0),P(W,0),P(W,H),P(0,H)};
  68. 	vector<P> chk;
  69. 	for(int i = 0 ; i < 4 ; i++) chk.push_back(vertex[i]);
  70. 	for(int i = 0 ; i < N ; i++){
  71. 		for(int j = 0 ; j < 4 ; j++){
  72. 			L l = L(vertex[j],vertex[(j+1)%4]);
  73. 			vector<P> g = crosspointCL(l,C(p[i],R));
  74. 			chk.insert(chk.end(),g.begin(),g.end());
  75. 		}
  76. 	}
  77. 	for(int i = 0 ; i < N ; i++){
  78. 		for(int j = i+1 ; j < N ; j++){
  79. 			vector<P> g = C_cp(C(p[i],R),C(p[j],R));
  80. 			chk.insert(chk.end(),g.begin(),g.end());
  81. 		}
  82. 	}
  83. 	bool bad = 0;
  84. 	for(int i = 0 ; i < chk.size() ; i++){
  85. 		for(int j = 0 ; j < 720 ; j++){
  86. 			P t = chk[i] + WEAK_EPS * memo[j];
  87. 			if( 0 < t.real()+EPS && t.real()-EPS < W &&
  88. 				0 < t.imag()+EPS && t.imag()-EPS < H
  89. 			){ // 四角形の中の点か？
  90. 				bool f = false;
  91. 				for(int k = 0 ; k < N ; k++){
  92. 					if(abs(t-p[k]) < R+EPS){
  93. 						f = true;
  94. 					}
  95. 				}
  96. 				bad |= !f;
  97. 			}
  98. 		}
  99. 	}
  100.  
  101. 	return !bad;
  102. }
  103.  
  104. double solver(int N,int W,int H,vector<P> p){
  105. 	for(int i = 0 ; i < 720 ; i++){
  106. 		memo[i] = P( cos( (PI / 360) * i ) , sin( (PI / 360) * i ) );
  107. 	}
  108. 	double l = 0 , r = 20000;
  109. 	while(r-l > EPS){
  110. 		double m = (l+r) / 2;
  111. 		if( check(N,W,H,p,m) ) r = m;
  112. 		else l = m;
  113. 	}
  114. 	return l;
  115. }
  116. int main(){
  117. 	int N;
  118. 	int W,H;
  119. 	cin >> W >> H;
  120. 	cin >> N;
  121. 	while(N>20){};
  122. 	vector<P> p;
  123.  
  124. 	for(int i = 0 ; i < N ; i++){
  125. 		int x,y;
  126. 		cin >> x >> y;
  127. 		p.push_back(P(x,y));
  128. 	}
  129. 	if(cin >> N) return 0;
  130. 	printf("%.6lf\n",solver(N,W,H,p));
  131. }
Success #stdin #stdout 0.02s 2876KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.000000
https://ideone.com/avx2i
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!