Advertisement
ivnikkk

Untitled

Nov 21st, 2022
530
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.45 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #define all(a) a.begin(), a.end()
  5. #define int long long
  6. mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  7. typedef long double ld;
  8. struct Point {
  9.     int x, y;
  10.     Point() : x(0), y(0) {}
  11.     Point(int _x, int _y) : x(_x), y(_y) {}
  12. };
  13. struct Line {
  14.     int a, b, c;
  15.     Line() : a(0), b(0), c(0) {}
  16.     Line(const Point& x, const Point& y) : a(y.y - x.y), b(x.x - y.x), c(x.y* y.x - y.y * x.x) {
  17.     }
  18.     bool operator==(const Line& other) const {
  19.         return a - other.a == 0 && b - other.b == 0 && c - other.c == 0;
  20.     }
  21. };
  22. unordered_map<int, int> ban;
  23.  
  24. const int mod1 = 1e9 + 7;
  25. int get_hsh(Point& x) {
  26.     return (x.x + x.y * 16063807ll) % mod1;
  27. }
  28. int time_cnt = 0;
  29. int line_cross(const Line& a, const Line& b, Point& ans) {
  30.     time_cnt += 4;
  31.     int d = (a.b * b.a - a.a * b.b);
  32.     if (d == 0)
  33.         return 0;
  34.     if (abs(b.b * a.c - b.c * a.b) % d || abs((b.c * a.a - a.c * b.a)) % d) {
  35.         return -1;
  36.     }
  37.     ans.x = (b.b * a.c - b.c * a.b) / d;
  38.     ans.y = (b.c * a.a - a.c * b.a) / d;
  39.     if (abs(ans.x) > 1e6 || abs(ans.y) > 1e6) {
  40.         return -1;
  41.     }
  42.     return 1;
  43. }
  44.  
  45. void break_point() {
  46.     time_cnt++;
  47.     if (time_cnt > 1e4) {
  48.         if ((double)clock() / (double)CLOCKS_PER_SEC >= 4.90000) {
  49.             cout << "No";
  50.             exit(0);
  51.         }
  52.         time_cnt = 0;
  53.     }
  54. }
  55. int n;
  56. vector<Point> arr;
  57. int count_f(vector<int>& p) {
  58.     vector<Line> x;
  59.     for (int i = 0; i + 1 < 2 * n; i += 2) {
  60.         break_point();
  61.         time_cnt += 3;
  62.         x.push_back(Line(arr[p[i]], arr[p[i + 1]]));
  63.     }
  64.     int rs = 0;
  65.     bool ok = 1;
  66.     unordered_map<int, pair<int, int>> re_hsh;
  67.     for (int i = 0; i < (int)x.size(); i++) {
  68.         for (int j = i + 1; j < (int)x.size(); j++) {
  69.             Point ins;
  70.             int indef = line_cross(x[i], x[j], ins);
  71.             if (indef == 1) {
  72.                 if (ban.find(get_hsh(ins)) != ban.end()) {
  73.                     ok = 0;
  74.                 }
  75.                 int h = get_hsh(ins);
  76.                 break_point();
  77.                 time_cnt += 4;
  78.                 re_hsh[h] = make_pair(ins.x, ins.y);
  79.                 break_point();
  80.                 rs++;
  81.             }
  82.             if (indef == -1) {
  83.                 ok = 0;
  84.                 int x_g = rnd();
  85.                 int y_g = rnd();
  86.                 x_g = abs(x_g) + 1000000;
  87.                 y_g = abs(y_g) + 1000000;
  88.                 Point gen(x_g, y_g);
  89.                 int h = get_hsh(gen);
  90.                 re_hsh[h] = make_pair(gen.x, gen.y);
  91.                 break_point();
  92.             }
  93.             break_point();
  94.  
  95.         }
  96.     }
  97.     if (ok && (int)re_hsh.size() == 1) {
  98.         cout << "Yes\n";
  99.         for (auto& it : re_hsh) {
  100.             cout << it.second.first<< ' ' << it.second.second;
  101.         }
  102.         exit(0);
  103.     }
  104.     return rs + 110 * n * (int)re_hsh.size();
  105. }
  106.  
  107. ld gen() {
  108.     int x = rnd() + 1;
  109.     int y = rnd() + 1;
  110.     break_point();
  111.     x %= y;
  112.     return (ld)x / (ld)y;
  113. }
  114. signed main() {
  115. #ifdef _DEBUG
  116.     freopen("input.txt", "r", stdin);
  117.     freopen("output.txt", "w", stdout);
  118. #endif
  119.     ios_base::sync_with_stdio(false);
  120.     cin.tie(nullptr);
  121.     cin >> n;
  122.     arr.resize(2 * n);
  123.     vector<int> p(2 * n);
  124.     for (int i = 0; i < 2 * n; i++) {
  125.         cin >> arr[i].x >> arr[i].y;
  126.         ban[get_hsh(arr[i])] = 1;
  127.         p[i] = i;
  128.     }
  129.     int m = 2 * n;
  130.     shuffle(all(p), mt19937(random_device()()));
  131.     int now = count_f(p);
  132.     ld t_[3] = { 1.00,10.00,1000 }, q_[3] = { 0.95,0.9995,0.9999 };
  133.     while (1) {
  134.         const ld eps = 1e-3;
  135.         ld t = t_[rnd() % 3], q = q_[rnd() % 3];
  136.         while (t > eps) {
  137.             break_point();
  138.             vector<int> _p = p;
  139.             break_point();
  140.             swap(_p[rnd() % m], _p[rnd() % m]);
  141.             int it = count_f(_p);
  142.             break_point();
  143.             if (gen() < exp((ld)(now - it) / (ld)t) || it < now) {
  144.                 p = _p;
  145.                 now = it;
  146.             }
  147.             break_point();
  148.             t *= q;
  149.         }
  150.     }
  151. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement