daily pastebin goal
8%
SHARE
TWEET

Untitled

a guest Jun 14th, 2018 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top