peltorator

!Выделение граней плоского графа

Feb 20th, 2018
124
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <set>
  4. #include <cmath>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <numeric>
  8. #include <ctime>
  9. #define _GLIBCXX_DEBUG
  10. #define _CRT_SECURE_NO_WARNINGS
  11. using namespace std;
  12.  
  13. typedef long long ll;
  14. typedef long double ld;
  15.  
  16. bool solve();
  17.  
  18. ll time()
  19. {
  20.     return (ll)clock() * 1000LL / CLOCKS_PER_SEC;
  21. }
  22.  
  23. int main()
  24. {
  25. //#ifdef ONLINE_JUDGE
  26.    // freopen("mirror.in", "r", stdin); freopen("mirror.out", "w", stdout);
  27. //#elif
  28.     //freopen("in.txt", "r", stdin);
  29. //#endif
  30.     int t = 1;
  31. #ifdef ONLINE_JUDGE
  32.     t = 1;
  33. #endif
  34.     while (t--)
  35.         solve();
  36. #ifndef ONLINE_JUDGE
  37. //  cerr << "time: " << time() << " ms" << endl;
  38. #endif
  39.     return 0;
  40. }
  41.  
  42. const ld eps1 = 1e-9;
  43. const ld eps2 = 1e-8;
  44.  
  45. struct Point
  46. {
  47.     ld x, y;
  48.     Point():
  49.         x(0),
  50.         y(0) {};
  51.     Point(ld x, ld y):
  52.         x(x),
  53.         y(y) {};
  54.     ld operator^(Point p)
  55.     {
  56.         return x * p.y - y * p.x;
  57.     }
  58.     ld operator*(Point p)
  59.     {
  60.         return x * p.x + y * p.y;
  61.     }
  62.     Point operator*(ld k)
  63.     {
  64.         return Point(x * k, y * k);
  65.     }
  66.     void operator*=(ld k)
  67.     {
  68.         x *= k;
  69.         y *= k;
  70.     }
  71.     bool operator==(Point p)
  72.     {
  73.         return abs(p.x - x) < eps1 && abs(p.y - y) < eps1;
  74.     }
  75.     Point operator+(Point p)
  76.     {
  77.         return Point(x + p.x, y + p.y);
  78.     }
  79.     void operator+=(Point p)
  80.     {
  81.         x += p.x;
  82.         y += p.y;
  83.     }
  84.     Point operator-(Point p)
  85.     {
  86.         return Point(x - p.x, y - p.y);
  87.     }
  88.     void operator-=(Point p)
  89.     {
  90.         x -= p.x;
  91.         y -= p.y;
  92.     }
  93.     void read()
  94.     {
  95.         ll X, Y;
  96.         cin >> X >> Y;
  97.         x = X;
  98.         y = Y;
  99.     }
  100.     void print()
  101.     {
  102.         cout << x << " " << y << "\n";
  103.     }
  104. };
  105.  
  106. struct Line
  107. {
  108.     ld a, b, c;
  109.     Line():
  110.         a(1),
  111.         b(0),
  112.         c(0) {}
  113.     Line(ld a, ld b, ld c):
  114.         a(a),
  115.         b(b),
  116.         c(c) {}
  117.     Line(Point p, Point q):
  118.         a(p.y - q.y),
  119.         b(q.x - p.x),
  120.         c(p.x * (q.y - p.y) + p.y * (p.x - q.x)) {}
  121.     ld operator()(Point p)
  122.     {
  123.         return a * p.x + b * p.y + c;
  124.     }
  125.     Point norm()
  126.     {
  127.         return Point(a, b);
  128.     }
  129.     Point dir()
  130.     {
  131.         return Point(-b, a);
  132.     }
  133.     void read()
  134.     {
  135.         ll A, B, C;
  136.         cin >> A >> B >> C;
  137.         c = C;
  138.         b = B;
  139.         a = A;
  140.     }
  141.     void print()
  142.     {
  143.         cout << a <<  " " << b << " " << c << "\n";
  144.     }
  145.     Line perp(Point p)
  146.     {
  147.         return Line(-b, a, p.x * b - a * p.y);
  148.     }
  149. };
  150.  
  151. const int N = 100000;
  152.  
  153. Line l[N];
  154.  
  155. vector<Point> q;
  156. set<int> kek[N];
  157. vector<int> mem[N], used[N];
  158. vector<pair<int, int> > g[N];
  159.  
  160. bool parallel(Line l, Line k)
  161. {
  162.     return abs(l.a * k.b - k.a * l.b) < eps1;
  163. }
  164.  
  165. Point intersect(Line l1, Line l2)
  166. {
  167.     Point p;
  168.     p.y = -(l1.a * l2.c - l2.a * l1.c) / (l1.a * l2.b - l2.a * l1.b);
  169.     p.x = -(l1.b * l2.c - l2.b * l1.c) / (l1.b * l2.a - l2.b * l1.a);
  170.     return p;
  171. }
  172.  
  173. bool cmp1(int a, int b)
  174. {
  175.     if (abs(q[a].x - q[b].x) > eps1)
  176.         return q[a].x < q[b].x;
  177.     return q[a].y < q[b].y;
  178. }
  179.  
  180. ld dist(Point p, Point q)
  181. {
  182.     return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));
  183. }
  184.  
  185. vector<ld> ans;
  186.  
  187. bool f(Point p)
  188. {
  189.     return p.y > eps1 || (abs(p.y) < eps1 && p.x > eps1);
  190. }
  191. Point curpoint;
  192. bool cmp2(pair<int, int> a, pair<int, int> b)
  193. {
  194.     Point v = q[a.first] - curpoint;
  195.     Point u = q[b.first] - curpoint;
  196.     bool x = f(v), y = f(u);
  197.     if (x != y)
  198.         return x;
  199.     return ((v ^ u) > 0);
  200. }
  201.  
  202. vector<Point> cur;
  203.  
  204. ld sq()
  205. {
  206.     int n = cur.size();
  207.     ld sum = 0;
  208.     for (int i = 1; i <= n; i++)
  209.     {
  210.         sum += (cur[i % n].x - cur[i - 1].x) * (cur[i % n].y + cur[i - 1].y) / (ld)2;
  211.         if (i == n)
  212.             return sum + (cur[0].x - cur[i % n].x) * (cur[0].y + cur[i % n].y) / (ld)2;
  213.     }
  214.     return 0;
  215. }
  216.  
  217.  
  218. bool solve()
  219. {
  220.     ios::sync_with_stdio(0);
  221.     cout.precision(100);
  222.     cerr.precision(5);
  223.     int n;
  224.     cin >> n;
  225.     for (int i = 0; i < n; i++)
  226.     {
  227.         Point P, Q;
  228.         P.read();
  229.         Q.read();
  230.         l[i] = Line(P, Q);
  231.     }
  232.     for (int i = 0; i < n; i++)
  233.         for (int j = i + 1; j < n; j++)
  234.             if (!parallel(l[i], l[j]))
  235.             {
  236.                 Point P = intersect(l[i], l[j]);
  237.                 bool ok = false;
  238.                 for (int k = 0; k < q.size(); k++)
  239.                     if (abs(P.x - q[k].x) < eps1 && abs(P.y - q[k].y) < eps1)
  240.                     {
  241.                         ok = true;
  242.                         kek[i].insert(k);
  243.                         kek[j].insert(k);
  244.                         break;
  245.                     }
  246.                 if (!ok)
  247.                 {
  248.                     kek[i].insert(q.size());
  249.                     kek[j].insert(q.size());
  250.                     q.push_back(P);
  251.                 }
  252.             }
  253.     for (int i = 0; i < n; i++)
  254.     {
  255.         for (auto it : kek[i])
  256.             mem[i].push_back(it);
  257.         sort(mem[i].begin(), mem[i].end(), cmp1);
  258.         for (int j = 1; j < mem[i].size(); j++)
  259.         {
  260.             int v = mem[i][j], u = mem[i][j - 1];
  261.           //  rev[v].push_back(g[u].size());
  262.             //rev[u].push_back(g[v].size());
  263.             g[v].push_back({u, g[u].size()});
  264.             g[u].push_back({v, g[v].size() - 1});
  265.             used[v].push_back(0);
  266.             used[u].push_back(0);
  267.         }
  268.     }
  269.     n = q.size();
  270.     for (int i = 0; i < n; i++)
  271.     {
  272.         curpoint = q[i];
  273.         sort(g[i].begin(), g[i].end(), cmp2);
  274.     }
  275.     for (int i = 0; i < n; i++)
  276.         for (int j = 0; j < g[i].size(); j++)
  277.         {
  278.             int k = 0;
  279.             while (g[g[i][j].first][k].first != i)
  280.                 k++;
  281.             g[i][j].second = k;
  282.         }
  283.     for (int i = 0; i < n; i++)
  284.         for (int j = 0; j < g[i].size(); j++)
  285.             if (!used[i][j])
  286.             {
  287.                 cur.clear();
  288.                 int v = i, cnt = j;
  289.                 while (!used[v][cnt])
  290.                 {
  291.                     cur.push_back(q[v]);
  292.                     used[v][cnt] = 1;
  293.                     int nextv = g[v][cnt].first;
  294.                     int nextcnt = g[v][cnt].second;
  295.                     v = nextv;
  296.                     cnt = nextcnt;
  297.                     cnt = (cnt + (int)g[v].size() - 1) % (int)g[v].size();
  298.                 }
  299.                // for (int i = 0; i < cur.size(); i++)
  300.                  //   cerr << cur[i].x << " " << cur[i].y << endl;
  301.               //  cout << endl;
  302.                 ld d = -sq();
  303.                 if (d > eps2)
  304.                     ans.push_back(d);
  305.             }
  306.     cout << ans.size();
  307.     sort(ans.begin(), ans.end());
  308.     for (int i = 0; i < ans.size(); i++)
  309.         cout << "\n" << ans[i];
  310.     return 0;
  311. }
RAW Paste Data