Advertisement
Guest User

Untitled

a guest
Dec 18th, 2018
196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.70 KB | None | 0 0
  1. //Konrad Paluszek, University of Warsaw (former XIV LO Warsaw)
  2. #ifndef LOCAL
  3. #pragma GCC optimize("O3")
  4. #endif
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define sim template <class c
  8. #define mor > muu & operator<< (
  9. #define ris return *this
  10. #define R22(r) sim> typename enable_if<1 r sizeof(dud<c>(0)), muu&>::type operator<<(c g) {
  11. sim> struct rge {c h, n;};
  12. sim> rge<c> range(c h, c n) {return rge<c>{h, n};}
  13. sim, class F> struct rgm {c h, n; F f;};
  14. sim, class F> rgm<c, F> map_range(c b, c e, F f) {return rgm<c, F>{b, e, f};}
  15. sim, class F> rgm<typename c::const_iterator, F> map_range(const c &x, F f) {return map_range(x.begin(), x.end(), f);}
  16. sim> auto dud(c *r) -> decltype(cerr << *r);
  17. sim> char dud(...);
  18. struct muu {
  19. #ifdef LOCAL
  20.     stringstream a;
  21.     ~muu() {cerr << a.str() << endl;}
  22.     R22(<) a << boolalpha << g; ris;}
  23.     R22(==) ris << range(begin(g), end(g));}
  24.     sim mor rge<c> u) {
  25.         a << '{';
  26.         for (c s = u.h; s != u.n; ++s)
  27.             *this << ", " + 2 * (s == u.h) << *s;
  28.         ris << '}';
  29.     }
  30.     sim, class n mor pair <c,n> r) {ris << "(" << r.first << ", " << r.second << ")";}
  31.     sim, class F mor rgm<c, F> u) {
  32.         for (c s = u.h; s != u.n; ++s)
  33.             u.f(*this << ", " + 2 * (s == u.h), *s);
  34.         ris;
  35.     }
  36.     #else
  37.     sim mor const c&) {ris;}
  38.     #endif
  39.     muu & operator()() {ris;}
  40. };
  41. #define debug (muu() << __FUNCTION__ << "#" << __LINE__ << ": ")
  42. #define imie(r) "[" #r ": " << (r) << "] "
  43. #define imask(r) "[" #r ": " << bitset<8 * sizeof(r)>(r) << "] "
  44. #define arr(a, i) "[" #a imie(i) ": " << a[i] << "] "
  45. #define arr2(a, i, j) "[" #a imie(i) imie(j) << ": " << a[i][j] << "] "
  46. #define f first
  47. #define s second
  48. #define vsv sim, class d, class e
  49. #define nop(o,c,r,l...) auto operator o(c a, r b)-> decltype(make_pair(l)) {return {l};}
  50. #define pcg(o) vsv, class f> nop(o, pair <c u d>, pair <e u f>, a.f o b.f, a.s o b.s) \
  51. vsv,class = typename enable_if<!is_same<c, muu>::value>::type> nop(o, c, pair<d u e>, a o b.f, a o b.s) \
  52. vsv> nop(o, pair<c u d>, e, a.f o b, a.s o b)
  53. #define clp(o) pcg(o) \
  54. vsv> void operator o##= (pair <c,d> & a, e b) {a.f o##= b; a.s o##= b;} \
  55. vsv, class f> void operator o##= (pair <c,d> & a, pair <e,f> b) {a.f o##= b.f; a.s o##= b.s;}
  56. #define syd(o) sim, class d> auto operator o(pair<c, d> e) -> decltype(make_pair(o e.f, o e.s)) {return {o e.f, o e.s};}
  57. #define u ,
  58. clp(+) clp(-) clp(*) clp(/) clp(%) clp(^) clp(|) clp(>>) clp(<<) clp(&) pcg(&&) pcg(||) syd(-) syd(+) syd(~) syd(!)
  59. #undef u
  60. sim> void mini(c &x, c y) {if (x > y) x = y;}
  61. sim> void maxi(c &x, c y) {if (x < y) x = y;}
  62. const int inf = 1e9;
  63. using pii = pair <int, int>;
  64. using ll = long long;
  65. const int nax = 111;
  66. pii in[nax][2];
  67. int n;
  68. void nope() {
  69.     printf("0.00000000000000000\n");
  70.     exit(0);
  71. }
  72. pii rot(pii x) {
  73.     return {x.second, -x.first};
  74. }
  75. using hpl = pair <pii, int>; //(v, m) = {x : sc(x, v) >= m}
  76. int sc(pii a, pii b) {
  77.     return a.first * b.first + a.second * b.second;
  78. }
  79. sim> c ve(pair <c, c> a, pair <c,c> b) {
  80.     return a.first * b.second - a.second * b.first;
  81. }
  82. vector <hpl> boundaries;
  83. void add(pii vec) {
  84.     vec = rot(vec);
  85.     int M = -inf, m = inf;
  86.     for (int i = 0; i < n; ++i) {
  87.         int l1 = sc(vec, in[i][0]);
  88.         int l2 = sc(vec, in[i][1]);
  89.         if (l1 > l2)
  90.             swap(l1, l2);
  91.         maxi(M, l1);
  92.         mini(m, l2);
  93.     }
  94.     if (m >= M) nope();
  95.     boundaries.emplace_back(vec, m);
  96.     boundaries.emplace_back(-vec, -M);
  97. }
  98. bool ang_cmp(hpl a, hpl b) {
  99.     if (a.first > pii(0, 0) && b.first < pii(0, 0))
  100.         return true;
  101.     if (a.first < pii(0, 0) && b.first > pii(0, 0))
  102.         return false;
  103.     return ve(a.first, b.first) > 0;
  104. }
  105. ll det(hpl a, hpl b, hpl c) {
  106.     ll r = a.first.first * b.first.second * 1ll * c.second
  107.         + b.first.first * c.first.second * 1ll * a.second
  108.         + c.first.first * a.first.second * 1ll * b.second
  109.         - b.first.first * a.first.second * 1ll * c.second
  110.         - a.first.first * c.first.second * 1ll * b.second
  111.         - c.first.first * b.first.second * 1ll * a.second;
  112.     return r;
  113. }
  114. int sign(int x) {
  115.     if (x > 0) return 1;
  116.     if (x < 0) return -1;
  117.     return 0;
  118. }
  119. bool subset(hpl a, hpl b) {
  120.     if (ve(a.first, b.first) || sc(a.first, b.first) < 0) return false;
  121.     return a.second * abs(b.first.first) >= b.second * abs(a.first.first) &&
  122.         a.second * abs(b.first.second) >= b.second * abs(a.first.second);
  123. }
  124. bool around(hpl a, hpl b, hpl c) {
  125.     int ab = ve(a.first, b.first);
  126.     int bc = ve(b.first, c.first);
  127.     int ca = ve(c.first, a.first);
  128.     return (ab >= 0 && bc >= 0 && ca >= 0) || (ab <= 0 && bc <= 0 && ca <= 0);
  129. }
  130. vector <hpl> find_hull(vector <hpl> vec) {
  131.     vector <hpl> hull;
  132.     int first = 0;
  133.     sort(vec.begin(), vec.end(), ang_cmp);
  134.     for (hpl curr : vec) {
  135.         if (!hull.empty() && subset(hull.back(), curr))
  136.             continue;
  137.         if (!hull.empty() && subset(curr, hull.back()))
  138.             hull.pop_back();
  139.         while (hull.size() - first >= 2u && det(hull.back(), hull[hull.size() - 2], curr) <= 0) {
  140.             if (around(hull[hull.size() - 2], hull.back(), curr))
  141.                 nope();
  142.             else
  143.                 hull.pop_back();
  144.         }
  145.         while (hull.size() - first >= 2u && det(curr, hull[first], hull[first + 1]) >= 0) {
  146.             if (around(curr, hull[first], hull[first + 1]))
  147.                 nope();
  148.             else
  149.                 first++;
  150.         }
  151.         if (hull.size() - first < 2u || det(hull.back(), curr, hull[first]) < 0)
  152.             hull.push_back(curr);
  153.     }
  154.     hull.erase(hull.begin(), hull.begin() + first);
  155.     return hull;
  156. }
  157. void hull_test() {
  158.     int m;
  159.     scanf("%d", &m);
  160.     vector <hpl> inn;
  161.     for (int i = 0; i < m; ++i) {
  162.         int a, b, c;
  163.         scanf("%d%d%d", &a, &b, &c);
  164.         inn.emplace_back(pii{a, b}, c);
  165.     }
  166.     vector <hpl> h = find_hull(inn);
  167.     debug << imie(h);
  168. }
  169. using ld = long double;
  170. using pdd = pair<ld, ld>;
  171. pdd intersect(hpl a, hpl b) {
  172.     int det = a.first.first * b.first.second - a.first.second * b.first.first;
  173.     int detx = a.second * b.first.second - a.first.second * b.second;
  174.     int dety = a.first.first * b.second - a.second * b.first.first;
  175.     assert(det != 0);
  176.     return {(ld) detx / det, (ld) dety / det};
  177. }
  178. int main(int argc, char **argv) {
  179.     if (argc == 2 && strcmp(argv[1], "test") == 0) {
  180.         hull_test();
  181.         return 0;
  182.     }
  183.     scanf("%d", &n);
  184.     for (int i = 0; i < n; ++i)
  185.         for (int j = 0; j < 2; ++j)
  186.             scanf("%d%d", &in[i][j].first, &in[i][j].second);
  187.     for (int i = 0; i < n; ++i)
  188.         for (int j = i + 1; j < n; ++j)
  189.             for (int k = 0; k < 2; ++k)
  190.                 for (int q = 0; q < 2; ++q)
  191.                     add(in[i][k] - in[j][q]);
  192.     for (int i = 0; i < n; ++i)
  193.         add(in[i][0] - in[i][1]);
  194.     vector <hpl> hull = find_hull(boundaries);
  195.     debug << imie(boundaries);
  196.     debug << imie(hull);
  197.     vector <pdd> points;
  198.     int h = hull.size();
  199.     for (int i = 0; i < h; ++i)
  200.         points.push_back(intersect(hull[i], i + 1 == h ? hull[0] : hull[i + 1]));
  201.     debug << imie(points);
  202.     ld area = 0;
  203.     for (int i = 0; i < h; ++i)
  204.         area += ve(points[i], i + 1 == h ? points[0] : points[i + 1]);
  205.     area /= 2;
  206.     printf("%.15lf\n", (double)area);
  207. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement