Advertisement
Guest User

Untitled

a guest
Jun 14th, 2018
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.74 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define _USE_MATH_DEFINES
  3.  
  4. #include <iostream>
  5. #include <string>
  6. #include <vector>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <set>
  10. #include <map>
  11. #include <ctime>
  12. #include <cstring>
  13. #include <iomanip>
  14. #include <random>
  15. #include <unordered_set>
  16. #include <unordered_map>
  17. #include <deque>
  18. #include <queue>
  19. #include <bitset>
  20. #include <sstream>
  21.  
  22. using namespace std;
  23.  
  24. #define mp make_pair
  25. #define X first
  26. #define Y second
  27. #define all(x) x.begin(), x.end()
  28. #define all_(x) x.rbegin(), x.rend()
  29.  
  30. typedef unsigned int ui;
  31. typedef unsigned long long ll;
  32. typedef double ld;
  33.  
  34. const int INF = 2e9 + 9;
  35. const int MAXN = 35e3 + 7;
  36. const ll MOD = 1e9 + 7;
  37. const ll ST = 157;
  38. const ll ST1 = 199;
  39. const ld EPS = 1e-7;
  40. const int BLOCK = 138;
  41.  
  42. void solve();
  43.  
  44. signed main(){
  45. srand('a' + 'l' + 'e' + 'x' + 'X' + '5' + '1' + '2');
  46. ios_base::sync_with_stdio(0);
  47. cin.tie(0);
  48. cout.tie(0);
  49. #ifdef _DEBUG
  50. freopen("input.txt", "r", stdin);
  51. freopen("output.txt", "w", stdout);
  52. #endif // _DEBUG
  53. solve();
  54. }
  55.  
  56. /*--------------------------------------------------------------------------------------------------*/
  57.  
  58. ld ans1 = 2 * M_PI;
  59.  
  60. struct line{
  61. ld a, b, c;
  62. line(pair<ld, ld> q1, pair<ld, ld> q2) : a(q2.Y - q1.Y), b(q1.X - q2.X), c(-a*q1.X - b*q1.Y) {}
  63. };
  64.  
  65. pair<ld, ld> operator -(pair<ld, ld> a, pair<ld, ld> b){
  66. return mp(a.first - b.first, a.second - b.second);
  67. }
  68.  
  69. pair<ld, ld> operator +(pair<ld, ld> a, pair<ld, ld> b){
  70. return mp(a.first + b.first, a.second + b.second);
  71. }
  72.  
  73. pair<ld, ld> operator /(pair<ld, ld> a, ld b){
  74. return mp(a.first / b, a.second / b);
  75. }
  76.  
  77. pair<ld, ld> operator *(pair<ld, ld> a, ld b){
  78. return mp(a.first * b, a.second * b);
  79. }
  80.  
  81. ld dot(pair<ld, ld> a, pair<ld, ld> b){
  82. return a.first * b.second - a.second * b.first;
  83. }
  84.  
  85. ld cros(pair<ld, ld> a, pair<ld, ld> b){
  86. return a.first * b.first + a.second * b.second;
  87. }
  88.  
  89. pair<ld, ld> alf(pair<ld, ld> a, pair<ld, ld> b, pair<ld, ld> st){
  90. ld t = atan2l(dot(a - st, b - st), cros(a - st, b - st));
  91. return mp(sinl(t), cosl(t));
  92. }
  93.  
  94. ld len(pair<ld, ld> a){
  95. return sqrtl(cros(a, a));
  96. }
  97.  
  98. pair<ld, ld> new_cord(pair<ld, ld> a, pair<ld, ld> dop, pair<ld, ld> st){
  99. pair<ld, ld> c = (a - st), c1 = c;
  100. c.first = (c1.first * dop.second - c1.second * dop.first);
  101. c.second = (c1.first * dop.first + c1.second * dop.second);
  102. return c + st;
  103. }
  104.  
  105. bool eq(pair<ld, ld> a, pair<ld, ld> b){
  106. return abs(a.first - b.first) < EPS && abs(a.second - b.second) < EPS;
  107. }
  108.  
  109. bool eq(ld a, ld b){
  110. return abs(a - b) < EPS;
  111. }
  112.  
  113. pair<ld, ld> start(pair<ld, ld> a1, pair<ld, ld> a2, pair<ld, ld> b1, pair<ld, ld> b2){
  114. auto pa1 = (a1 + a2) / 2.0;
  115. auto pb1 = (b1 + b2) / 2.0;
  116. a1 = mp(a1.second, -a1.first);
  117. a2 = mp(a2.second, -a2.first);
  118. b1 = mp(b1.second, -b1.first);
  119. b2 = mp(b2.second, -b2.first);
  120. auto pa2 = pa1 + a1 - a2;
  121. auto pb2 = pb1 + b1 - b2;
  122. if (eq(dot(pa1 - pa2, pb1 - pb2), 0)){
  123. a1 = mp(-a1.second, a1.first);
  124. a2 = mp(-a2.second, a2.first);
  125. b1 = mp(-b1.second, b1.first);
  126. b2 = mp(-b2.second, b2.first);
  127. if (eq(dot(a1 - b1, a2 - b2), 0)){
  128. if (eq(dot(a1 - b1, a2 - b1), 0)){
  129. return (max({ a1, a2, b1, b2 }) + min({ a1, a2, b1, b2 })) / 2.0;
  130. }
  131. return mp(INF, INF);
  132. }
  133. line q1(a1, b1), q2(a2, b2);
  134. return mp((q1.b * q2.c - q2.b * q1.c) / (q1.a * q2.b - q2.a * q1.b), (q1.a * q2.c - q2.a * q1.c) / (q1.a * q2.b - q2.a * q1.b));
  135. }
  136. line q1(pa1, pa2), q2(pb1, pb2);
  137. return mp((q1.b * q2.c - q2.b * q1.c) / (q1.a * q2.b - q2.a * q1.b), (q1.a * q2.c - q2.a * q1.c) / (q1.a * q2.b - q2.a * q1.b));
  138. }
  139.  
  140. void get(int n, pair<ld, ld> st, pair<ld, ld> a, vector<pair<ld, ld>> &v1, vector<pair<ld, ld>> &v2){
  141. for (int j = 1; j < n; j++){
  142. auto now = new_cord(v1[j], a, st);
  143. bool b = 1;
  144. for (int i = 0; i < n && b; i++){
  145. if (eq(now, v2[i])){
  146. b = 0;
  147. }
  148. }
  149. if(!b){
  150. if (j == n - 1){
  151. ld ans = atan2(a.first, a.second);
  152. if (ans < 0){
  153. ans += 2 * M_PI;
  154. }
  155. ans1 = min(ans1, ans);
  156. }
  157. continue;
  158. }
  159. break;
  160. }
  161. }
  162.  
  163. void solve(){
  164. int n;
  165. cin >> n;
  166. vector<pair<ld, ld>> v1(n), v2(n);
  167. for (auto &i : v1){
  168. cin >> i.first >> i.second;
  169. }
  170. for (auto &i : v2){
  171. cin >> i.first >> i.second;
  172. }
  173. sort(all(v2));
  174. for (int i = 0; i < n; i++){
  175. for (int j = 0; j < n; j++){
  176. if (eq(len(v2[i] - v2[j]), len(v1[0] - v1[1]))){
  177. auto t = start(v1[0], v2[i], v1[1], v2[j]);
  178. auto p = alf(v1[0], v2[i], t);
  179. if (v1[0] == v2[i]) p = alf(v1[1], v2[j], t);
  180. if(!eq(t,mp(INF, INF))) get(n, t, p, v1, v2);
  181. t = start(v1[0], v2[j], v1[1], v2[i]);
  182. p = alf(v1[0], v2[j], t);
  183. if (v1[0] == v2[j]) p = alf(v1[1], v2[i], t);
  184. if (!eq(t, mp(INF, INF))) get(n, t, p, v1, v2);
  185. }
  186. }
  187. }
  188. cout << fixed << setprecision(6) << ans1;
  189. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement