fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <string.h>
  3. #include <string>
  4. #include <stdio.h>
  5. #include <iostream>
  6. #include <sstream>
  7.  
  8. #include <queue>
  9. #include <deque>
  10. #include <map>
  11. #include <vector>
  12. #include <set>
  13.  
  14. #include <algorithm>
  15. #include <math.h>
  16. #include <time.h>
  17. #include <assert.h>
  18. using namespace std;
  19. typedef  long long ll;
  20.  
  21. #define _(a, b) memset((a), (b), sizeof(a))
  22. #define REP(i, a, b) for(int i = (a); i < (b); ++i)
  23. #define REPD(i, a, b) for(int i = (b) - 1; i >= (a); --i) 
  24. #define ITER(it, V) for(__typeof((V).begin()) it = (V).begin(); it != (V).end(); ++it)
  25. #define all(a) a.begin(),a.end()
  26. #define mp make_pair
  27. #define pb push_back
  28. #define fs first
  29. #define sc second
  30. #define pii pair<int, int> 
  31. template<typename T> int size(T& a) { return (int)a.size(); }
  32. template<typename T> T sqr(T a) {return a * a; }
  33.  
  34. struct pt {
  35. 	double x, y ;
  36. 	pt(double x =0, double y = 0) :  x(x), y(y) {}
  37. 	void scan(){
  38. 		cin >> y >> x;
  39. 	}
  40. 	pt operator + (const pt& o) {
  41. 		return pt(x + o.x, y + o.y);
  42. 	}
  43. 	pt operator - (const pt & o) {
  44. 		return pt(x - o.x, y - o.y);
  45. 	}
  46. 	pt operator * (const double& d) {
  47. 		return pt(x * d, y * d);
  48. 	}
  49. 	pt operator / (const double& d) {
  50. 		return pt(x / d, y / d);
  51. 	}
  52. 	double operator ^ (const pt &  o) {
  53. 		return x * o.y - y * o.x;
  54. 	}
  55. 	pt rotate(double alpha) {
  56. 		double nx = x * cos(alpha) - y * sin(alpha);
  57. 		double ny = x * sin(alpha) + y * cos(alpha);
  58. 		return pt(nx, ny);
  59. 	}
  60. 	double length(const pt& o) {
  61. 		return sqrt(sqr(x - o.x) + sqr(y - o.y));
  62. 	}
  63. 	void setLength(const double &d) {
  64. 		double z = sqrt(sqr(x) + sqr(y));
  65. 		x = x / z * d;
  66. 		y = y / z * d;
  67. 	}
  68. } ;
  69.  
  70. pt a[51];
  71. double ans = 1e9;
  72. double all = 0;
  73. int n;
  74. const double EPS = 1e-7;
  75. const double PI = asin(1.0) * 2;
  76. void calcAll() {
  77. 	double s =0 ;
  78. 	REP(i, 0, n) s += a[i] ^ a[(i + 1) % n];
  79. 	s = fabs(s) / 2;
  80. 	all = s;
  81. }
  82. double square(pt a, pt b, pt c) {
  83. 	return fabs((a ^ b) + (b ^ c) + (c ^ a)) / 2;
  84. }
  85.  
  86. bool Equal(double a, double b){
  87. 	return fabs(a - b) < EPS;
  88. }
  89. bool Less(double a, double b){
  90. 	return a + EPS < b;
  91. }
  92. bool Great(double a, double b) {
  93. 	return a > b + EPS;
  94. }
  95. double getAngle(double a, double b, double c) {
  96. 	// c * c = a * a + b * b - 2 * a * b * cos(alpha)
  97. 	// alpha = acos( c * c - a  * a - b * b / (-2 * a * b)) ;
  98. 	return acos( (sqr(c) - sqr(a) - sqr(b)) / (- 2 * a * b)) ;
  99. }
  100. pt calc(pt a, pt b, pt c, double need) {
  101. 	double alpha = getAngle(a.length(b), b.length(c), a.length(c));
  102. 	double res = 2 * need / (sin(alpha) * a.length(b));
  103. 	double O = sqrt(sqr(res) + sqr(a.length(b)) - 2 * res * a.length(b) * cos(alpha));
  104. 	double g = asin(res * sin(alpha) / O);
  105. 	pt gg = (b - a);
  106. 	gg = gg.rotate(-g);
  107. 	gg.setLength(O);
  108. 	// end - beg = vec
  109. 	pt r = gg + a;
  110. 	return r;
  111. }
  112. pt go(pt x, int &nxt) {
  113. 	double cur = 0;
  114. 	while (1) {
  115. 		double d = square(x, a[nxt], a[(nxt + 1) % n]);
  116. 		if (Equal(cur + d, all / 2)) {
  117. 			pt ret = a[(nxt + 1) % n];
  118. 			return ret;
  119. 		} else if (Less(cur + d, all / 2)) {
  120. 			nxt = (nxt + 1) % n;
  121. 		} else {
  122. 			pt ret = calc(x, a[nxt], a[(nxt + 1) % n], all / 2 - cur);
  123. 			return ret;
  124. 		}
  125. 		cur += d;
  126. 	}
  127. }
  128. bool btw(pt a, pt b, pt c) {
  129. 	return Equal(a.length(b), a.length(c) + b.length(c));
  130. }
  131. vector<pt> build(pt a, pt b, int r){
  132. 	int n1 , n2 ;
  133. 	n1 = r;
  134. 	n2 = n1;
  135. 	pt c = go(a, n1);
  136. 	pt d = go(b, n2);
  137.  
  138.  
  139. 	static vector<pt> res ;
  140. 	res.clear();
  141.  
  142. 	for(int i = n1; ; i = (i + 1) % n){
  143.  
  144. 		if (btw(::a[i], ::a[(i + 1) % n], c) && btw(::a[i], ::a[(i + 1) % n], d)) {
  145. 			res.pb (c);
  146. 			res.pb (d);
  147. 			break;
  148. 		}  else if (btw(::a[i], ::a[(i + 1) % n], c)) {
  149. 			res.pb (c);
  150. 		} else if ( btw(::a[i], ::a[(i + 1) % n], d)) {
  151. 			res.pb(::a[i]);
  152. 			res.pb (d);
  153. 			break;
  154. 		} else {
  155. 			res.pb(::a[i]);
  156. 		}
  157.  
  158. 		if (i == n2) break;
  159. 	}
  160. 	return res;
  161. }
  162. void solve() {
  163. 	scanf("%d", &n);
  164. 	REP(i, 0, n) a[i].scan();
  165. 	calcAll();
  166. 	REP(i, 0, n) {
  167. 		vector<pt> tmp = build(a[i], a[(i + 1) % n], i);
  168. 		vector<int> idx(size(tmp));
  169. 		REP(z, 0, size(tmp)) {
  170. 			REP(j, 0, n) if (btw(a[j], a[(j + 1) % n], tmp[z])) 
  171. 				idx[z] = (j + 1) % n;
  172. 		}
  173. 		REP(j, 0, size(tmp) - 1) {
  174. 			pt L = tmp[j], R = tmp[j + 1];
  175. 			REP(iter,0,70) {
  176. 				pt M1 = L + (R - L) / 3;
  177. 				pt M2 = R - (R - L) / 3;
  178. 				int tt = idx[j];
  179. 				pt P1 = go(M1, tt);
  180. 				tt = idx[j];
  181. 				pt P2 = go(M2, tt);
  182. 				double f1 = P1.length(M1);
  183. 				double f2 = P2.length(M2);
  184. 				if (Less(f1 , f2)) {
  185. 					R = M2;
  186. 				} else {
  187. 					L = M1;
  188. 				}
  189. 				ans = min(ans, f1);
  190. 				ans = min(ans, f2);
  191. 			}
  192. 		}
  193. 	}
  194. 	printf("%.10lf", ans);
  195. }
  196. int main() { 
  197. #ifdef air
  198. 	freopen("input.txt", "r", stdin);
  199. 	freopen("output.txt", "w", stdout);
  200. #endif
  201.  
  202. 	solve();
  203.  
  204.  
  205.  
  206.  
  207. #ifdef air
  208. 	printf("\n\n%.3lf", (clock()  ) * 1e-3);
  209. #endif
  210.  
  211. }
Success #stdin #stdout 0.02s 2732KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000.0000000000
https://ideone.com/M9RHL
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!