RectangleCrossings.cpp

#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pi pair<int,int>
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define ln(x) ((int)x.length())
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define dbg(x) cout << #x << ": " << x << endl
#define clr(x,v) memset(x, v, sizeof(x))
#define dblout(x) cout << setprecision(x) << fixed;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const int eps = 1e-9;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
const int MAXN = 1e6 + 5;

// POINT
typedef int ftype;
// const ftype eps = 1e-9;
struct point
{
    ftype x, y;
    point() {}
    point(ftype x, ftype y): x(x), y(y) {}
    point operator+(const point &p)
    {
        return point(x + p.x, y + p.y);
    }
    point operator-(const point &p)
    {
        return point(x - p.x, y - p.y);
    }
    point operator*(const ftype &s)
    {
        return point(x * s, y * s);
    }
    point operator/(const ftype &s)
    {
        return point(x / s, y / s); // be careful, zero division error
    }
    // bool operator<(const point &p) const
    // {
    //     return x < p.x - eps || (abs(x - p.x) < eps && y < p.y - eps);
    // }
    // For integers
    bool operator<(const point &p) const
    {
        return x < p.x || (x == p.x && y < p.y);
    }
    // bool operator==(const point &p) const
    // {
    //     return fabs(x - p.x) < eps && fabs(y - p.y) < eps;
    // }
    // For integers
    bool operator==(const point &p) const
    {
        return x == p.x && y == p.y;
    }
    ftype cross(const point &p)
    {
        return x * p.y - p.x * y;
    }
    ftype cross(const point &a, const point &b)
    {
        return (*this - a).cross(*this - b);
    }
};

class RectangleCrossings
{
public:
    vector <int> countAreas(vector <string>, vector <string>);
};

bool inside(vector<point> &r, point p)
{
    int x1 = r[0].x, y1 = r[0].y;
    int x2 = r[1].x, y2 = r[1].y;
    return p.x > x1 && p.x < x2 && p.y > y1 && p.y < y2;
}

int length2(point a, point b)
{
    return ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int ccw(point a, point b, point c)
{
    point v1(b - a), v2(c - a);
    int t = v1.cross(v2);

    if (t > 0)
        return +1;
    if (t < 0)
        return -1;
    if (v1.x * v2.x < 0 || v1.y * v2.y < 0)
        return -1;
    if (length2(v1, point(0, 0)) < length2(v2, point(0, 0)))
        return +1;
    return 0;
}

bool intersect(point p1, point p2, point p3, point p4)
{
    // special case handling if a segment is just a point
    bool x = (p1 == p2), y = (p3 == p4);
    if(x && y)  return p1 == p3;
    if(x)   return ccw(p3, p4, p1) == 0;
    if(y)   return ccw(p1, p2, p3) == 0;

    return  ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0  &&
            ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0;
}

vector <int> RectangleCrossings::countAreas(vector <string> rectangles, vector <string> segments)
{
    vector<vector<point>> rect, seg;
    for(auto s : rectangles)
    {
        point p, q;
        stringstream ss(s);
        ss >> p.x >> p.y >> q.x >> q.y;
        rect.pb({p, q});
    }
    for(auto s : segments)
    {
        point p, q;
        stringstream ss(s);
        ss >> p.x >> p.y >> q.x >> q.y;
        seg.pb({p, q});
    }
    int n = sz(rect), m = sz(seg);
    int inside_area = 0, inter_area = 0;

    for(int i = 0; i < n; i++)
    {
        bool in = false;
        for(int j = 0; j < m; j++)
            in |= inside(rect[i], seg[j][0]), in |= inside(rect[i], seg[j][1]);
        if(in)
            inside_area += (rect[i][1].x - rect[i][0].x) * (rect[i][1].y - rect[i][0].y);

        bool inter = false;
        int x1 = rect[i][0].x, y1 = rect[i][0].y;
        int x2 = rect[i][1].x, y2 = rect[i][1].y;
        for(int j = 0; j < m; j++)
        {
            inter |= intersect(point(x1, y1), point(x2, y1), seg[j][0], seg[j][1]);
            inter |= intersect(point(x2, y1), point(x2, y2), seg[j][0], seg[j][1]);
            inter |= intersect(point(x2, y2), point(x1, y2), seg[j][0], seg[j][1]);
            inter |= intersect(point(x1, y2), point(x1, y1), seg[j][0], seg[j][1]);
        }

        if(inter && !in)
            inter_area += (rect[i][1].x - rect[i][0].x) * (rect[i][1].y - rect[i][0].y);
    }

    return {inside_area, inter_area};
}
// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.4 (beta) modified by pivanof
bool KawigiEdit_RunTest(int testNum, vector <string> p0, vector <string> p1, bool hasAnswer, vector <int> p2)
{
    cout << "Test " << testNum << ": [" << "{";
    for (int i = 0; int(p0.size()) > i; ++i)
    {
        if (i > 0)
        {
            cout << ",";
        }
        cout << "\"" << p0[i] << "\"";
    }
    cout << "}" << "," << "{";
    for (int i = 0; int(p1.size()) > i; ++i)
    {
        if (i > 0)
        {
            cout << ",";
        }
        cout << "\"" << p1[i] << "\"";
    }
    cout << "}";
    cout << "]" << endl;
    RectangleCrossings *obj;
    vector <int> answer;
    obj = new RectangleCrossings();
    clock_t startTime = clock();
    answer = obj->countAreas(p0, p1);
    clock_t endTime = clock();
    delete obj;
    bool res;
    res = true;
    cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
    if (hasAnswer)
    {
        cout << "Desired answer:" << endl;
        cout << "\t" << "{";
        for (int i = 0; int(p2.size()) > i; ++i)
        {
            if (i > 0)
            {
                cout << ",";
            }
            cout << p2[i];
        }
        cout << "}" << endl;
    }
    cout << "Your answer:" << endl;
    cout << "\t" << "{";
    for (int i = 0; int(answer.size()) > i; ++i)
    {
        if (i > 0)
        {
            cout << ",";
        }
        cout << answer[i];
    }
    cout << "}" << endl;
    if (hasAnswer)
    {
        if (answer.size() != p2.size())
        {
            res = false;
        }
        else
        {
            for (int i = 0; int(answer.size()) > i; ++i)
            {
                if (answer[i] != p2[i])
                {
                    res = false;
                }
            }
        }
    }
    if (!res)
    {
        cout << "DOESN'T MATCH!!!!" << endl;
    }
    else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2)
    {
        cout << "FAIL the timeout" << endl;
        res = false;
    }
    else if (hasAnswer)
    {
        cout << "Match :-)" << endl;
    }
    else
    {
        cout << "OK, but is it right?" << endl;
    }
    cout << "" << endl;
    return res;
}
int main()
{
    bool all_right;
    all_right = true;

    vector <string> p0;
    vector <string> p1;
    vector <int> p2;

    {
        // ----- test 0 -----
        string t0[] = {"-1000 -1000 1000 1000"};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        string t1[] = {"-525 245 222 243"};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        int t2[] = {4000000, 0};
        p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
        all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
        // ------------------
    }

    {
        // ----- test 1 -----
        string t0[] = {"1 1 2 2", "1 4 2 5", "5 5 6 7", "7 7 9 9"};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        string t1[] = {"1 2 1 5"};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        int t2[] = {0, 2};
        p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
        all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
        // ------------------
    }

    {
        // ----- test 2 -----
        string t0[] = {"1 1 3 3", "4 4 5 5", "6 6 7 7", "8 8 9 9", "51 22 344 352", "-124 -235 -12 -1"};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        string t1[] = {"-100 -2 300 300"};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        int t2[] = {122898, 0};
        p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
        all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
        // ------------------
    }

    {
        // ----- test 3 -----
        string t0[] = {"1 1 3 3", "4 4 5 5", "6 6 7 7", "8 8 9 9", "51 22 344 352", "-124 -235 -12 -1"};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        string t1[] = {"-104 -103 202 201"};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        int t2[] = {122898, 7};
        p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
        all_right = KawigiEdit_RunTest(3, p0, p1, true, p2) && all_right;
        // ------------------
    }

    {
        // ----- test 4 -----
        string t0[] = {"-891 -869 -853 -842", "-857 -399 -744 -231", "-910 -55 -856 36", "-844 287 -749 548", "-809 627 -782 954", "-704 -803 -641 -663", "-684 -330 -558 -268", "-702 -40 -545 98", "-660 386 -528 586", "-697 855 -571 962", "-414 -678 -168 -648", "-401 -559 -383 -441", "-387 5 -263 51", "-389 220 -194 448", "-361 673 -175 753", "68 -912 95 -742", "-24 -521 24 -227", "30 -70 38 -2", "-111 297 14 356", "7 797 27 809", "368 -709 418 -614", "247 -453 344 -251", "385 -111 417 -33", "275 202 290 421", "265 604 278 921", "524 -861 655 -640", "555 -336 576 -305", "429 28 578 35", "480 324 704 520", "444 632 665 842", "932 -954 981 -931", "930 -537 939 -455", "735 -81 787 192", "830 316 869 589", "808 629 971 666"};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        string t1[] = {"-898 -383 126 12", "283 -716 545 -918", "-299 333 54 138", "-901 129 706 488", "-8 690 -290 955", "-590 -771 476 257", "-528 -518 651 -139", "-984 -848 -380 459", "-358 924 31 -617", "817 -904 -208 -401", "-657 -211 275 -407", "-427 -699 -460 876", "403 -612 -675 563", "-782 -197 845 816", "-492 -771 -342 -83", "-650 -208 393 -614", "-67 -290 135 -610", "68 650 -366 560", "-482 608 -525 516", "548 460 -95 -436", "461 -457 -491 -846", "-672 728 -764 548", "-301 633 -613 278", "-496 126 940 576", "-350 -378 -671 1000", "148 82 275 211", "815 872 -810 -362", "160 -367 -754 569", "-721 941 -405 -57", "-792 582 804 563", "-934 -115 -641 -737"};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        int t2[] = {126942, 241757};
        p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
        all_right = KawigiEdit_RunTest(4, p0, p1, true, p2) && all_right;
        // ------------------
    }

    if (all_right)
    {
        cout << "You're a stud (at least on the example cases)!" << endl;
    }
    else
    {
        cout << "Some of the test cases had errors." << endl;
    }
    return 0;
}
// END KAWIGIEDIT TESTING



//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!