fork(1) download
copy 
  1.  
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <cmath>
  7.  
  8. using namespace std;
  9.  
  10. const int maxn = 11111;
  11. const double eps = 1e-6;
  12. struct point_t {
  13.     double x, y;
  14. 	point_t() { }
  15. 	point_t(double tx, double ty) {
  16. 		x = tx, y = ty;
  17. 	}
  18. 	point_t operator-(const point_t &r) const {
  19. 		return point_t(x - r.x, y - r.y);
  20. 	}
  21. 	point_t operator+(const point_t &r) const {
  22. 		return point_t(x + r.x, y + r.y);
  23. 	}
  24. 	point_t operator/(const double &r) {
  25. 		return point_t(x / r, y / r);
  26. 	}
  27. 	point_t operator*(const double &r) {
  28. 		return point_t(x * r, y * r);
  29. 	}
  30. } p[maxn], tp[maxn], sk[maxn];
  31. int n, top;
  32. double S, R;
  33.  
  34. double cross(point_t p1, point_t p2) {
  35. 	return p1.x * p2.y - p1.y * p2.x;
  36. }
  37.  
  38. double sqr(double x) { return x * x; }
  39. double dist(point_t p1, point_t p2) {
  40. 	p2 = p2 - p1;
  41. 	return sqrt(sqr(p2.x) + sqr(p2.y));
  42. }
  43.  
  44. point_t normalize(point_t p) {
  45. 	double l = sqrt(sqr(p.x) + sqr(p.y));
  46. 	return p / l;
  47. }
  48.  
  49. int dblcmp(double x) {
  50. 	return x < -eps ? -1 : x > eps;
  51. }
  52.  
  53. bool cmp(const point_t &p1, const point_t &p2) {
  54. 	return dblcmp(p1.y - p2.y) == 0 ? p1.x < p2.x : p1.y < p2.y;
  55. }
  56.  
  57. void graham() {
  58. 	sort(p + 1, p + 1 + n, cmp);
  59. 	top = 2, sk[1] = p[1], sk[2] = p[2];
  60. 	for (int i = 3; i <= n; ++i) {
  61. 		while (top >= 2 && dblcmp(cross(p[i] - sk[top - 1], sk[top] - sk[top - 1])) >= 0) --top;
  62. 		sk[++top] = p[i];
  63. 	}
  64. 	int ttop = top;
  65. 	for (int i = n - 1; i >= 1; --i) {
  66. 		while (top > ttop && dblcmp(cross(p[i] - sk[top - 1], sk[top] - sk[top - 1])) >= 0) --top;
  67. 		sk[++top] = p[i];
  68. 	}
  69. 	--top;
  70. 	n = top;
  71. 	for (int i = 1; i <= n; ++i) {
  72. 		p[i] = sk[i];
  73. 	}
  74. }
  75.  
  76. point_t inter(point_t a, point_t b, point_t c, point_t d) {
  77. 	point_t p1 = b - a, p2 = d - c;
  78. 	double a1 = p1.y, b1 = -p1.x, c1;
  79. 	double a2 = p2.y, b2 = -p2.x, c2;
  80. 	c1 = a1 * a.x + b1 * a.y;
  81. 	c2 = a2 * c.x + b2 * c.y;
  82. 	return point_t((c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1), (c1 * a2 - c2 * a1) / (b1 * a2 - b2 * a1));
  83. }
  84.  
  85. void extend(double d) {
  86. 	p[0] = p[n]; p[n + 1] = p[1];
  87. 	for (int i = 1; i <= n; ++i) {
  88. 		point_t p1 = p[i - 1], p2 = p[i], p3 = p[i + 1];
  89. 		point_t v1 = normalize(p2 - p1);
  90. 		swap(v1.x, v1.y);
  91. 		v1.y = -v1.y;
  92. 		point_t v2 = normalize(p3 - p2);
  93. 		swap(v2.x, v2.y);
  94. 		v2.y = -v2.y;	   
  95. 		v1 = v1 * d, v2 = v2 * d;
  96. 		tp[i] = inter(p1 + v1, p2 + v1, p2 + v2, p3 + v2);  
  97. 	}
  98. }
  99.  
  100. char buf[1024];
  101.  
  102. double area() {
  103. 	double ans = 0;
  104. 	for (int i = 2; i <= n; ++i) {
  105. 		ans += cross(tp[i - 1] - tp[1], tp[i] - tp[1]);
  106. 	}
  107. 	return fabs(ans) / 2;
  108. }
  109.  
  110. double maxdist() {
  111. 	tp[0] = tp[n], p[0] = p[n];
  112. 	int to = 0;
  113. 	double ans = 0;
  114. 	for (int i = 0; i < n; ++i) {
  115. 		while ((to + 1) % n != i && dblcmp(fabs(cross(tp[i + 1] - tp[i], p[to] - tp[i])) - fabs(cross(tp[i + 1] - tp[i], p[to + 1] - tp[i]))) <= 0) to = (to + 1) % n;
  116. 		ans = max(ans, dist(tp[i], p[to]));
  117. 		ans = max(ans, dist(tp[i + 1], p[to]));
  118. 	}
  119. 	return ans;
  120. }
  121.  
  122. double work1() {
  123. 	double begin = 0, end = 1e15, mid;
  124. 	while (begin + 1e-9 < end) {
  125. 		mid = (begin + end) / 2;
  126. 		extend(mid);
  127. 		double a = area();
  128. 		if (a < S) {
  129. 			begin = mid;
  130. 		} else {
  131. 			end = mid;
  132. 		}
  133. 	}
  134. 	return end;
  135. }
  136.  
  137. double work2() {
  138. 	double begin = 0, end = 1e15, mid;
  139. 	while (begin + 1e-9 < end) {
  140. 		mid = (begin + end) / 2;
  141. 		extend(mid);
  142. 		double d = maxdist();
  143. 		if (d > R) {
  144. 			end = mid;
  145. 		} else {
  146. 			begin = mid;
  147. 		}
  148. 	}
  149. 	return begin;
  150. }
  151.  
  152. int main() {
  153. 	while (scanf("%d", &n) != EOF) {
  154. 		for (int i = 1; i <= n; ++i) {
  155. 			scanf("%s", buf);
  156. 			sscanf(buf, "(%lf,%lf)", &p[i].x, &p[i].y);
  157. 		}
  158. 		scanf("%lf%lf", &S, &R);
  159. 		graham();
  160. 		double ans1 = work1(), ans2 = work2();
  161. 		bool flag1 = true, flag2 = true;
  162. 		extend(ans1);
  163. 		if (dblcmp(area() - S) < 0) flag1 = false;
  164. 		extend(ans2);
  165. 		if (dblcmp(maxdist() - R) > 0) flag2 = false;
  166. 		if (dblcmp(ans1 - ans2) > 0 || !flag1 || !flag2) {
  167. 			puts("no appropriate design");
  168. 		} else {
  169. 			if (ans1 > ans2) swap(ans1, ans2);
  170. 			printf("%.3lf %.3lf\n", ans1, ans2);
  171. 		}
  172. 	}
  173. 	return 0;
  174. }
Success #stdin #stdout 0s 3376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/d6fmzv
language:
C++ (gcc 8.3)
created:
10 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!