• API
• FAQ
• Tools
• Archive
daily pastebin goal
47%
SHARE
TWEET

# Untitled

a guest Nov 21st, 2018 112 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. #include "jngen.h"
3. using namespace std;
4. #define forn(i, n) for (int i = 0; i < int(n); ++i)
5.
6. jngen::Dsu dsu;
7.
8. int n = 1000;
9. vector<Point> p;
10.
11. double dist(Point x, Point y) {
12.     double dx = x.x - y.x;
13.     double dy = x.y - y.y;
14.     return sqrt(dx*dx+dy*dy);
15. }
16.
17. vector<vector<int>> e;
18. vector<int> b;
19. vector<int> res;
20.
21. void dfs(int v) {
22.     b[v] = 1;
23.     res.push_back(v);
24.     for (int to: e[v]) {
25.         if (!b[to]) dfs(to);
26.     }
27. }
28.
29. bool intersect(int l1, int r1, int l2, int r2) {
30.     return max(l1, l2) <= min(r1, r2);
31. }
32.
33. bool segmentsIntersect(Point a, Point b, Point c, Point d) {
34.     if (!intersect(min(a.x, b.x), max(a.x, b.x), min(c.x, d.x), max(c.x, d.x))) return false;
35.     if (!intersect(min(a.y, b.y), max(a.y, b.y), min(c.y, d.y), max(c.y, d.y))) return false;
36.     for (int i = 0; i < 2; ++i) {
37.         long long s1 = (c-a) % (b-a);
38.         long long s2 = (d-a) % (b-a);
39.         assert(s1 != 0 && s2 != 0);
40.         if ((s1 < 0) == (s2 < 0)) return false;
41.     }
42.     return true;
43. }
44.
45. vector<Point> runFix(vector<Point> p) {
46.     bool done = true;
47.     int n = p.size();
48.     while (done) {
49.         cerr << "Fixing..." << endl;
50.         done = false;
51.         for (int i = 0; i < n; ++i) {
52.             for (int j = i+2; j < n; ++j) {
53.                 if ((j+1)%n == i) continue;
54.                 if (segmentsIntersect(p[i], p[i+1], p[j], p[(j+1)%n])) {
55.                     reverse(p.begin() + i + 1, p.begin() + j + 1);
56.                     done = true;
57.                 }
58.             }
59.         }
60.     }
61.     return p;
62. }
63.
64. int main(int argc, char *argv[]) {
65.     // registerGen(argc, argv);
66.     parseArgs(argc, argv);
67.
68.     p = rndg.pointsInGeneralPosition(n, 100000).shuffled();
69.     vector<pair<int, int>> es;
70.     forn(i, n) forn(j, i) es.emplace_back(i, j);
71.     sort(es.begin(), es.end(), [&](pair<int, int> x, pair<int, int> y) {
72.         return dist(p[x.first], p[x.second]) < dist(p[y.first], p[y.second]);
73.     });
74.     e.resize(n);
75.     b.resize(n);
76.     for (auto ee: es) {
77.         int x, y;
78.         tie(x, y) = ee;
79.         if (dsu.unite(x, y)) {
80.             e[x].push_back(y);
81.             e[y].push_back(x);
82.         }
83.     }
84.     mt19937 rr;
85.     forn(i, n) shuffle(e[i].begin(), e[i].end());
86.     dfs(0);
87.
88.     // Uncomment this line to try random order instead of MST order.
89.     // res = Array::id(n).shuffle();
90.
91.     res.push_back(res[0]);
92.
93.     Drawer d;
94.     for (auto pp: p) d.point(pp);
95.     forn(i, n) d.segment(p[res[i]], p[res[i+1]]);
96.     d.dumpSvg("image.svg");
97.
98.     vector<Point> fixed;
99.     forn(i, n) fixed.push_back(p[res[i]]);
100.     fixed = runFix(fixed);
101.
102.     d = Drawer();
103.     for (auto pp: p) d.point(pp);
104.     forn(i, n) d.segment(fixed[i], fixed[(i+1)%n]);
105.     d.dumpSvg("image_fixed.svg");
106. }
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.

Top