Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Konrad Paluszek, University of Warsaw (former XIV LO Warsaw)
- #ifndef LOCAL
- #pragma GCC optimize("O3")
- #endif
- #include <bits/stdc++.h>
- using namespace std;
- #define sim template <class c
- #define mor > muu & operator<< (
- #define ris return *this
- #define R22(r) sim> typename enable_if<1 r sizeof(dud<c>(0)), muu&>::type operator<<(c g) {
- sim> struct rge {c h, n;};
- sim> rge<c> range(c h, c n) {return rge<c>{h, n};}
- sim, class F> struct rgm {c h, n; F f;};
- sim, class F> rgm<c, F> map_range(c b, c e, F f) {return rgm<c, F>{b, e, f};}
- sim, class F> rgm<typename c::const_iterator, F> map_range(const c &x, F f) {return map_range(x.begin(), x.end(), f);}
- sim> auto dud(c *r) -> decltype(cerr << *r);
- sim> char dud(...);
- struct muu {
- #ifdef LOCAL
- stringstream a;
- ~muu() {cerr << a.str() << endl;}
- R22(<) a << boolalpha << g; ris;}
- R22(==) ris << range(begin(g), end(g));}
- sim mor rge<c> u) {
- a << '{';
- for (c s = u.h; s != u.n; ++s)
- *this << ", " + 2 * (s == u.h) << *s;
- ris << '}';
- }
- sim, class n mor pair <c,n> r) {ris << "(" << r.first << ", " << r.second << ")";}
- sim, class F mor rgm<c, F> u) {
- for (c s = u.h; s != u.n; ++s)
- u.f(*this << ", " + 2 * (s == u.h), *s);
- ris;
- }
- #else
- sim mor const c&) {ris;}
- #endif
- muu & operator()() {ris;}
- };
- #define debug (muu() << __FUNCTION__ << "#" << __LINE__ << ": ")
- #define imie(r) "[" #r ": " << (r) << "] "
- #define imask(r) "[" #r ": " << bitset<8 * sizeof(r)>(r) << "] "
- #define arr(a, i) "[" #a imie(i) ": " << a[i] << "] "
- #define arr2(a, i, j) "[" #a imie(i) imie(j) << ": " << a[i][j] << "] "
- #define f first
- #define s second
- #define vsv sim, class d, class e
- #define nop(o,c,r,l...) auto operator o(c a, r b)-> decltype(make_pair(l)) {return {l};}
- #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) \
- 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) \
- vsv> nop(o, pair<c u d>, e, a.f o b, a.s o b)
- #define clp(o) pcg(o) \
- vsv> void operator o##= (pair <c,d> & a, e b) {a.f o##= b; a.s o##= b;} \
- vsv, class f> void operator o##= (pair <c,d> & a, pair <e,f> b) {a.f o##= b.f; a.s o##= b.s;}
- #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};}
- #define u ,
- clp(+) clp(-) clp(*) clp(/) clp(%) clp(^) clp(|) clp(>>) clp(<<) clp(&) pcg(&&) pcg(||) syd(-) syd(+) syd(~) syd(!)
- #undef u
- sim> void mini(c &x, c y) {if (x > y) x = y;}
- sim> void maxi(c &x, c y) {if (x < y) x = y;}
- const int inf = 1e9;
- using pii = pair <int, int>;
- using ll = long long;
- const int nax = 111;
- pii in[nax][2];
- int n;
- void nope() {
- printf("0.00000000000000000\n");
- exit(0);
- }
- pii rot(pii x) {
- return {x.second, -x.first};
- }
- using hpl = pair <pii, int>; //(v, m) = {x : sc(x, v) >= m}
- int sc(pii a, pii b) {
- return a.first * b.first + a.second * b.second;
- }
- sim> c ve(pair <c, c> a, pair <c,c> b) {
- return a.first * b.second - a.second * b.first;
- }
- vector <hpl> boundaries;
- void add(pii vec) {
- vec = rot(vec);
- int M = -inf, m = inf;
- for (int i = 0; i < n; ++i) {
- int l1 = sc(vec, in[i][0]);
- int l2 = sc(vec, in[i][1]);
- if (l1 > l2)
- swap(l1, l2);
- maxi(M, l1);
- mini(m, l2);
- }
- if (m >= M) nope();
- boundaries.emplace_back(vec, m);
- boundaries.emplace_back(-vec, -M);
- }
- bool ang_cmp(hpl a, hpl b) {
- if (a.first > pii(0, 0) && b.first < pii(0, 0))
- return true;
- if (a.first < pii(0, 0) && b.first > pii(0, 0))
- return false;
- return ve(a.first, b.first) > 0;
- }
- ll det(hpl a, hpl b, hpl c) {
- ll r = a.first.first * b.first.second * 1ll * c.second
- + b.first.first * c.first.second * 1ll * a.second
- + c.first.first * a.first.second * 1ll * b.second
- - b.first.first * a.first.second * 1ll * c.second
- - a.first.first * c.first.second * 1ll * b.second
- - c.first.first * b.first.second * 1ll * a.second;
- return r;
- }
- int sign(int x) {
- if (x > 0) return 1;
- if (x < 0) return -1;
- return 0;
- }
- bool subset(hpl a, hpl b) {
- if (ve(a.first, b.first) || sc(a.first, b.first) < 0) return false;
- return a.second * abs(b.first.first) >= b.second * abs(a.first.first) &&
- a.second * abs(b.first.second) >= b.second * abs(a.first.second);
- }
- bool around(hpl a, hpl b, hpl c) {
- int ab = ve(a.first, b.first);
- int bc = ve(b.first, c.first);
- int ca = ve(c.first, a.first);
- return (ab >= 0 && bc >= 0 && ca >= 0) || (ab <= 0 && bc <= 0 && ca <= 0);
- }
- vector <hpl> find_hull(vector <hpl> vec) {
- vector <hpl> hull;
- int first = 0;
- sort(vec.begin(), vec.end(), ang_cmp);
- for (hpl curr : vec) {
- if (!hull.empty() && subset(hull.back(), curr))
- continue;
- if (!hull.empty() && subset(curr, hull.back()))
- hull.pop_back();
- while (hull.size() - first >= 2u && det(hull.back(), hull[hull.size() - 2], curr) <= 0) {
- if (around(hull[hull.size() - 2], hull.back(), curr))
- nope();
- else
- hull.pop_back();
- }
- while (hull.size() - first >= 2u && det(curr, hull[first], hull[first + 1]) >= 0) {
- if (around(curr, hull[first], hull[first + 1]))
- nope();
- else
- first++;
- }
- if (hull.size() - first < 2u || det(hull.back(), curr, hull[first]) < 0)
- hull.push_back(curr);
- }
- hull.erase(hull.begin(), hull.begin() + first);
- return hull;
- }
- void hull_test() {
- int m;
- scanf("%d", &m);
- vector <hpl> inn;
- for (int i = 0; i < m; ++i) {
- int a, b, c;
- scanf("%d%d%d", &a, &b, &c);
- inn.emplace_back(pii{a, b}, c);
- }
- vector <hpl> h = find_hull(inn);
- debug << imie(h);
- }
- using ld = long double;
- using pdd = pair<ld, ld>;
- pdd intersect(hpl a, hpl b) {
- int det = a.first.first * b.first.second - a.first.second * b.first.first;
- int detx = a.second * b.first.second - a.first.second * b.second;
- int dety = a.first.first * b.second - a.second * b.first.first;
- assert(det != 0);
- return {(ld) detx / det, (ld) dety / det};
- }
- int main(int argc, char **argv) {
- if (argc == 2 && strcmp(argv[1], "test") == 0) {
- hull_test();
- return 0;
- }
- scanf("%d", &n);
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < 2; ++j)
- scanf("%d%d", &in[i][j].first, &in[i][j].second);
- for (int i = 0; i < n; ++i)
- for (int j = i + 1; j < n; ++j)
- for (int k = 0; k < 2; ++k)
- for (int q = 0; q < 2; ++q)
- add(in[i][k] - in[j][q]);
- for (int i = 0; i < n; ++i)
- add(in[i][0] - in[i][1]);
- vector <hpl> hull = find_hull(boundaries);
- debug << imie(boundaries);
- debug << imie(hull);
- vector <pdd> points;
- int h = hull.size();
- for (int i = 0; i < h; ++i)
- points.push_back(intersect(hull[i], i + 1 == h ? hull[0] : hull[i + 1]));
- debug << imie(points);
- ld area = 0;
- for (int i = 0; i < h; ++i)
- area += ve(points[i], i + 1 == h ? points[0] : points[i + 1]);
- area /= 2;
- printf("%.15lf\n", (double)area);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement