fork download

copy

/*
    Mongy wrote this shit
*/
 
#include <bits/stdc++.h>
 
 
using namespace std;
#define ll long long
#define ld long double
#define nl cout << '\n'
#define pri(n) cout<<fixed<<setprecision(n)
#define d5l_arr(arr, n) for(int i = 0 ; i < n ; i ++)cin >> arr[i]
#define all(arr) arr.begin(), arr.end()
 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
void m4_htgeb_tle_kda_ya3ny() {
    cin.tie(0);
    cin.sync_with_stdio(0);
    cout.tie(0);
    cout.sync_with_stdio(0);
}
 
const int N = 1e6 + 1, inf = 1e9 + 10;
const ll mod = 1e9 + 7, infl = 1e18 + 10;
 
#define pt pair<int, int>
#define x first
#define y second
#define T double
#define pd pair<T, T>
 
pt operator-(pt a, pt b){return {a.x - b.x, a.y - b.y }; }
ll cross(pt a, pt b){ return  a.x * b.y - a.y * b.x ; }
ld cross(pd a, pd b){ return  a.x * b.y - a.y * b.x ; }
ll orient(pt a, pt b, pt c){return cross(a - b, c - b);}
pd operator/(pt a, T f){ return {(T)a.x / f, (T)a.y / f}; }
pt operator*(pt a, ll f){ return {a.x * f, a.y * f}; }
 
bool properInter(pt a, pt b, pt c, pt d, pd &out) {
    double oa = orient(c,d,a),
            ob = orient(c,d,b),
            oc = orient(a,b,c),
            od = orient(a,b,d);
    // Proper intersection exists iff opposite signs
    if (oa*ob < 0 && oc*od < 0) {out = (a*ob - b*oa) / (ob-oa); return true;}
    return false;
}
 
int orientation(pd a, pd b, pd c) {
    double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
    if (v < 0) return -1; // clockwise
    if (v > 0) return +1; // counter-clockwise
    return 0;
}
 
bool cw(pd a, pd b, pd c, bool include_collinear) {
    int o = orientation(a, b, c);
    return o < 0 || (include_collinear && o == 0);
}
bool collinear(pd a, pd b, pd c) { return orientation(a, b, c) == 0; }
 
void convex_hull(vector<pd>& a, bool include_collinear = false) {
    pd p0 = *min_element(a.begin(), a.end(), [](pd a, pd b) {
        return make_pair(a.y, a.x) < make_pair(b.y, b.x);
    });
    sort(a.begin(), a.end(), [&p0](const pd& a, const pd& b) {
        int o = orientation(p0, a, b);
        if (o == 0)
            return (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y)
                   < (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);
        return o < 0;
    });
    if (include_collinear) {
        int i = (int)a.size()-1;
        while (i >= 0 && collinear(p0, a[i], a.back())) i--;
        reverse(a.begin()+i+1, a.end());
    }
 
    vector<pd> st;
    for (int i = 0; i < (int)a.size(); i++) {
        while (st.size() > 1 && !cw(st[st.size()-2], st.back(), a[i], include_collinear))
            st.pop_back();
        st.push_back(a[i]);
    }
 
    if (include_collinear == false && st.size() == 2 && st[0] == st[1])
        st.pop_back();
 
    a = st;
}
 
 
bool above(pt a, pt p) { return p.y >= a.y;}
 
bool crossesRay(pt a, pt p, pt q) {return (above(a,q) - above(a,p)) * orient(a,p,q) > 0;}
 
bool inPolygon(vector<pt> p, pt a, bool strict = true) {
    int numCrossings = 0;
    for (int i = 0, n = p.size(); i < n; i++) {
        numCrossings += crossesRay(a, p[i], p[(i+1)%n]); }
    return numCrossings & 1;
}
 
void solveCase() {
    int n, m;
    cin >> n >> m;
    vector<pt > a(n), b(m);
    for (auto &p: a) cin >> p.x >> p.y;
    for (auto &p: b) cin >> p.x >> p.y;
    vector<pd > arr;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            pt x = a[i], y = a[(i + 1) % n], u = b[j], v = b[(j + 1) % m];
            pd out;
            bool inter = properInter(x, y, u, v, out);
            if (inter) arr.push_back(out);
        }
    }
 
    for(auto p: a){if (inPolygon(b, p)) arr.push_back(p);}
    for(auto p: b){if (inPolygon(a, p)) arr.push_back(p);}
 
    if (arr.size() <= 2){ return cout << 0.0000, void(); }
    convex_hull(arr, false);
    n = (int)arr.size();
    ld ans = 0;
    for(int i = 0; i < n; i ++){
        ans += cross(arr[i], arr[(i + 1) % n]);
    }
    cout << fabs(ans) * .5;
}
 
 
signed main() {
    m4_htgeb_tle_kda_ya3ny();
    int test = 1;
    cin >> test;
    pri(4);
    for (int i = 1; i <= test; ++i) {
        solveCase();
        nl;
    }
    return 0;
}

Main.java:5: error: illegal character: '#'
#include <bits/stdc++.h>
^
Main.java:5: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
Main.java:9: error: illegal character: '#'
#define ll long long
^
Main.java:9: error: class, interface, or enum expected
#define ll long long
        ^
Main.java:10: error: illegal character: '#'
#define ld long double
^
Main.java:11: error: illegal character: '#'
#define nl cout << '\n'
^
Main.java:12: error: illegal character: '#'
#define pri(n) cout<<fixed<<setprecision(n)
^
Main.java:13: error: illegal character: '#'
#define d5l_arr(arr, n) for(int i = 0 ; i < n ; i ++)cin >> arr[i]
^
Main.java:13: error: class, interface, or enum expected
#define d5l_arr(arr, n) for(int i = 0 ; i < n ; i ++)cin >> arr[i]
                                        ^
Main.java:13: error: class, interface, or enum expected
#define d5l_arr(arr, n) for(int i = 0 ; i < n ; i ++)cin >> arr[i]
                                                ^
Main.java:14: error: illegal character: '#'
#define all(arr) arr.begin(), arr.end()
^
Main.java:21: error: class, interface, or enum expected
    cin.sync_with_stdio(0);
    ^
Main.java:22: error: class, interface, or enum expected
    cout.tie(0);
    ^
Main.java:23: error: class, interface, or enum expected
    cout.sync_with_stdio(0);
    ^
Main.java:24: error: class, interface, or enum expected
}
^
Main.java:27: error: class, interface, or enum expected
const ll mod = 1e9 + 7, infl = 1e18 + 10;
^
Main.java:29: error: illegal character: '#'
#define pt pair<int, int>
^
Main.java:29: error: class, interface, or enum expected
#define pt pair<int, int>
        ^
Main.java:30: error: illegal character: '#'
#define x first
^
Main.java:31: error: illegal character: '#'
#define y second
^
Main.java:32: error: illegal character: '#'
#define T double
^
Main.java:33: error: illegal character: '#'
#define pd pair<T, T>
^
Main.java:35: error: class, interface, or enum expected
pt operator-(pt a, pt b){return {a.x - b.x, a.y - b.y }; }
                                                         ^
Main.java:36: error: class, interface, or enum expected
ll cross(pt a, pt b){ return  a.x * b.y - a.y * b.x ; }
                                                      ^
Main.java:37: error: class, interface, or enum expected
ld cross(pd a, pd b){ return  a.x * b.y - a.y * b.x ; }
                                                      ^
Main.java:38: error: class, interface, or enum expected
ll orient(pt a, pt b, pt c){return cross(a - b, c - b);}
                                                       ^
Main.java:39: error: class, interface, or enum expected
pd operator/(pt a, T f){ return {(T)a.x / f, (T)a.y / f}; }
                                                          ^
Main.java:40: error: class, interface, or enum expected
pt operator*(pt a, ll f){ return {a.x * f, a.y * f}; }
                                                     ^
Main.java:48: error: class, interface, or enum expected
    if (oa*ob < 0 && oc*od < 0) {out = (a*ob - b*oa) / (ob-oa); return true;}
    ^
Main.java:48: error: class, interface, or enum expected
    if (oa*ob < 0 && oc*od < 0) {out = (a*ob - b*oa) / (ob-oa); return true;}
                                                                ^
Main.java:48: error: class, interface, or enum expected
    if (oa*ob < 0 && oc*od < 0) {out = (a*ob - b*oa) / (ob-oa); return true;}
                                                                            ^
Main.java:50: error: class, interface, or enum expected
}
^
Main.java:54: error: class, interface, or enum expected
    if (v < 0) return -1; // clockwise
    ^
Main.java:55: error: class, interface, or enum expected
    if (v > 0) return +1; // counter-clockwise
    ^
Main.java:56: error: class, interface, or enum expected
    return 0;
    ^
Main.java:57: error: class, interface, or enum expected
}
^
Main.java:61: error: class, interface, or enum expected
    return o < 0 || (include_collinear && o == 0);
    ^
Main.java:62: error: class, interface, or enum expected
}
^
Main.java:63: error: class, interface, or enum expected
bool collinear(pd a, pd b, pd c) { return orientation(a, b, c) == 0; }
                                                                     ^
Main.java:68: error: class, interface, or enum expected
    });
    ^
Main.java:69: error: class, interface, or enum expected
    sort(a.begin(), a.end(), [&p0](const pd& a, const pd& b) {
    ^
Main.java:71: error: class, interface, or enum expected
        if (o == 0)
        ^
Main.java:74: error: class, interface, or enum expected
        return o < 0;
        ^
Main.java:75: error: class, interface, or enum expected
    });
    ^
Main.java:76: error: class, interface, or enum expected
    if (include_collinear) {
    ^
Main.java:78: error: class, interface, or enum expected
        while (i >= 0 && collinear(p0, a[i], a.back())) i--;
        ^
Main.java:79: error: class, interface, or enum expected
        reverse(a.begin()+i+1, a.end());
        ^
Main.java:80: error: class, interface, or enum expected
    }
    ^
Main.java:83: error: class, interface, or enum expected
    for (int i = 0; i < (int)a.size(); i++) {
    ^
Main.java:83: error: class, interface, or enum expected
    for (int i = 0; i < (int)a.size(); i++) {
                    ^
Main.java:83: error: class, interface, or enum expected
    for (int i = 0; i < (int)a.size(); i++) {
                                       ^
Main.java:86: error: class, interface, or enum expected
        st.push_back(a[i]);
        ^
Main.java:87: error: class, interface, or enum expected
    }
    ^
Main.java:92: error: class, interface, or enum expected
    a = st;
    ^
Main.java:93: error: class, interface, or enum expected
}
^
Main.java:96: error: class, interface, or enum expected
bool above(pt a, pt p) { return p.y >= a.y;}
                                           ^
Main.java:98: error: class, interface, or enum expected
bool crossesRay(pt a, pt p, pt q) {return (above(a,q) - above(a,p)) * orient(a,p,q) > 0;}
                                                                                        ^
Main.java:102: error: class, interface, or enum expected
    for (int i = 0, n = p.size(); i < n; i++) {
    ^
Main.java:102: error: class, interface, or enum expected
    for (int i = 0, n = p.size(); i < n; i++) {
                                  ^
Main.java:102: error: class, interface, or enum expected
    for (int i = 0, n = p.size(); i < n; i++) {
                                         ^
Main.java:103: error: class, interface, or enum expected
        numCrossings += crossesRay(a, p[i], p[(i+1)%n]); }
                                                         ^
Main.java:105: error: class, interface, or enum expected
}
^
Main.java:109: error: class, interface, or enum expected
    cin >> n >> m;
    ^
Main.java:110: error: class, interface, or enum expected
    vector<pt > a(n), b(m);
    ^
Main.java:111: error: class, interface, or enum expected
    for (auto &p: a) cin >> p.x >> p.y;
    ^
Main.java:112: error: class, interface, or enum expected
    for (auto &p: b) cin >> p.x >> p.y;
    ^
Main.java:113: error: class, interface, or enum expected
    vector<pd > arr;
    ^
Main.java:114: error: class, interface, or enum expected
    for (int i = 0; i < n; i++) {
    ^
Main.java:114: error: class, interface, or enum expected
    for (int i = 0; i < n; i++) {
                    ^
Main.java:114: error: class, interface, or enum expected
    for (int i = 0; i < n; i++) {
                           ^
Main.java:115: error: class, interface, or enum expected
        for (int j = 0; j < m; j++) {
                        ^
Main.java:115: error: class, interface, or enum expected
        for (int j = 0; j < m; j++) {
                               ^
Main.java:117: error: class, interface, or enum expected
            pd out;
            ^
Main.java:118: error: class, interface, or enum expected
            bool inter = properInter(x, y, u, v, out);
            ^
Main.java:119: error: class, interface, or enum expected
            if (inter) arr.push_back(out);
            ^
Main.java:120: error: class, interface, or enum expected
        }
        ^
Main.java:123: error: class, interface, or enum expected
    for(auto p: a){if (inPolygon(b, p)) arr.push_back(p);}
                                                         ^
Main.java:124: error: class, interface, or enum expected
    for(auto p: b){if (inPolygon(a, p)) arr.push_back(p);}
                                                         ^
Main.java:126: error: class, interface, or enum expected
    if (arr.size() <= 2){ return cout << 0.0000, void(); }
                                                         ^
Main.java:128: error: class, interface, or enum expected
    n = (int)arr.size();
    ^
Main.java:129: error: class, interface, or enum expected
    ld ans = 0;
    ^
Main.java:130: error: class, interface, or enum expected
    for(int i = 0; i < n; i ++){
    ^
Main.java:130: error: class, interface, or enum expected
    for(int i = 0; i < n; i ++){
                   ^
Main.java:130: error: class, interface, or enum expected
    for(int i = 0; i < n; i ++){
                          ^
Main.java:132: error: class, interface, or enum expected
    }
    ^
Main.java:134: error: class, interface, or enum expected
}
^
Main.java:139: error: class, interface, or enum expected
    int test = 1;
    ^
Main.java:140: error: class, interface, or enum expected
    cin >> test;
    ^
Main.java:141: error: class, interface, or enum expected
    pri(4);
    ^
Main.java:142: error: class, interface, or enum expected
    for (int i = 1; i <= test; ++i) {
    ^
Main.java:142: error: class, interface, or enum expected
    for (int i = 1; i <= test; ++i) {
                    ^
Main.java:142: error: class, interface, or enum expected
    for (int i = 1; i <= test; ++i) {
                               ^
Main.java:144: error: class, interface, or enum expected
        nl;
        ^
Main.java:145: error: class, interface, or enum expected
    }
    ^
Main.java:147: error: class, interface, or enum expected
}
^
95 errors

Standard output is empty