Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- #define int long long
- mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
- typedef long double ld;
- struct Point {
- int x, y;
- Point() : x(0), y(0) {}
- Point(int _x, int _y) : x(_x), y(_y) {}
- };
- struct Line {
- int a, b, c;
- Line() : a(0), b(0), c(0) {}
- 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) {
- }
- bool operator==(const Line& other) const {
- return a - other.a == 0 && b - other.b == 0 && c - other.c == 0;
- }
- };
- unordered_map<int, int> ban;
- const int mod1 = 1e9 + 7;
- int get_hsh(Point& x) {
- return (x.x + x.y * 16063807ll) % mod1;
- }
- int time_cnt = 0;
- int line_cross(const Line& a, const Line& b, Point& ans) {
- time_cnt += 4;
- int d = (a.b * b.a - a.a * b.b);
- if (d == 0)
- return 0;
- if (abs(b.b * a.c - b.c * a.b) % d || abs((b.c * a.a - a.c * b.a)) % d) {
- return -1;
- }
- ans.x = (b.b * a.c - b.c * a.b) / d;
- ans.y = (b.c * a.a - a.c * b.a) / d;
- if (abs(ans.x) > 1e6 || abs(ans.y) > 1e6) {
- return -1;
- }
- return 1;
- }
- void break_point() {
- time_cnt++;
- if (time_cnt > 1e4) {
- if ((double)clock() / (double)CLOCKS_PER_SEC >= 4.90000) {
- cout << "No";
- exit(0);
- }
- time_cnt = 0;
- }
- }
- int n;
- vector<Point> arr;
- int count_f(vector<int>& p) {
- vector<Line> x;
- for (int i = 0; i + 1 < 2 * n; i += 2) {
- break_point();
- time_cnt += 3;
- x.push_back(Line(arr[p[i]], arr[p[i + 1]]));
- }
- int rs = 0;
- bool ok = 1;
- unordered_map<int, pair<int, int>> re_hsh;
- for (int i = 0; i < (int)x.size(); i++) {
- for (int j = i + 1; j < (int)x.size(); j++) {
- Point ins;
- int indef = line_cross(x[i], x[j], ins);
- if (indef == 1) {
- if (ban.find(get_hsh(ins)) != ban.end()) {
- ok = 0;
- }
- int h = get_hsh(ins);
- break_point();
- time_cnt += 4;
- re_hsh[h] = make_pair(ins.x, ins.y);
- break_point();
- rs++;
- }
- if (indef == -1) {
- ok = 0;
- int x_g = rnd();
- int y_g = rnd();
- x_g = abs(x_g) + 1000000;
- y_g = abs(y_g) + 1000000;
- Point gen(x_g, y_g);
- int h = get_hsh(gen);
- re_hsh[h] = make_pair(gen.x, gen.y);
- break_point();
- }
- break_point();
- }
- }
- if (ok && (int)re_hsh.size() == 1) {
- cout << "Yes\n";
- for (auto& it : re_hsh) {
- cout << it.second.first<< ' ' << it.second.second;
- }
- exit(0);
- }
- return rs + 110 * n * (int)re_hsh.size();
- }
- ld gen() {
- int x = rnd() + 1;
- int y = rnd() + 1;
- break_point();
- x %= y;
- return (ld)x / (ld)y;
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> n;
- arr.resize(2 * n);
- vector<int> p(2 * n);
- for (int i = 0; i < 2 * n; i++) {
- cin >> arr[i].x >> arr[i].y;
- ban[get_hsh(arr[i])] = 1;
- p[i] = i;
- }
- int m = 2 * n;
- shuffle(all(p), mt19937(random_device()()));
- int now = count_f(p);
- ld t_[3] = { 1.00,10.00,1000 }, q_[3] = { 0.95,0.9995,0.9999 };
- while (1) {
- const ld eps = 1e-3;
- ld t = t_[rnd() % 3], q = q_[rnd() % 3];
- while (t > eps) {
- break_point();
- vector<int> _p = p;
- break_point();
- swap(_p[rnd() % m], _p[rnd() % m]);
- int it = count_f(_p);
- break_point();
- if (gen() < exp((ld)(now - it) / (ld)t) || it < now) {
- p = _p;
- now = it;
- }
- break_point();
- t *= q;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement