#include <stdio.h>
#include <assert.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

typedef pair <int, int> point;
typedef pair <point, point> lineSeg;

enum eventType {EVENT_END, EVENT_VERTICAL, EVENT_START};
typedef pair <int, int> xValLineMap;
typedef pair <xValLineMap, eventType> event;

int main () {
    int lineCounter = 0, numberOfLines, intersectionCounter = 0;
    point p1, p2;
    lineSeg l;
    vector <lineSeg> lineSegSet;
    int xVal, yVal;

    cout << "Enter the number of lines" << endl;
    cout << "All x and y coordinates should be distinct" << endl;
    cin >> numberOfLines;

    // Take in the line first as coordinate pairs
    while (lineCounter < numberOfLines) {
        cout << "Enter x1:" << endl;
        cin >> xVal;
        cout << "Enter y1:" << endl;
        cin >> yVal;
        p1 = make_pair (xVal, yVal);

        cout << "Enter x2:" << endl;
        cin >> xVal;
        cout << "Enter y2:" << endl;
        cin >> yVal;
        p2 = make_pair (xVal, yVal);

        l = make_pair (p1, p2);
        lineSegSet.push_back (l);
        lineCounter++;
    }

    vector <event> evSet;
    xValLineMap x1;
    event e1, e2;

    // Process the lineSegset and create the event queue
    for (int i = 0; i < lineSegSet.size(); i++) {
        if (lineSegSet[i].first.second != lineSegSet[i].second.second) { 
            // vertical line with same xCoordinate
            // Create a lineId to xVal pair
            xValLineMap x1 = make_pair (lineSegSet[i].first.first, i);
            // Create a lineMap event with the attribute
            e1 = make_pair (x1, EVENT_VERTICAL);
            evSet.push_back (e1);
        }
        else if (lineSegSet[i].first.first != lineSegSet[i].second.first) { 
            // Horizontal line with same yCoordinate
            xValLineMap x1 = make_pair (lineSegSet[i].first.first, i);
            xValLineMap x2 = make_pair (lineSegSet[i].second.first, i);
            e1 = make_pair (x1, EVENT_START);
            e2 = make_pair (x2, EVENT_END);
            evSet.push_back (e1);
            evSet.push_back (e2);
        }
        else {
            assert (0);
        }
    }

    cout << "EventSet unsorted on x-cordinate" << endl;
    for (int i = 0; i < evSet.size(); i++) {
        cout << evSet[i].first.first << "," << evSet[i].first.second << "," << evSet[i].second << endl;
    }

    sort (evSet.begin(), evSet.end());

    cout << "Eventset sorted on x-cordinate" << endl;
    for (int i = 0; i < evSet.size(); i++) {
        cout << evSet[i].first.first << "," << evSet[i].first.second << "," << evSet[i].second << endl;
    }

    multiset <int> pEvSet;

    // Looking for intersections
    for (int i = 0; i < evSet.size(); i++) {
        event e = evSet[i];
        switch (e.second)
        {
            case EVENT_START: 
            {
                pEvSet.insert(lineSegSet[e.first.second].first.second);
                break;
            }
            case EVENT_END:
            {
                pEvSet.erase(pEvSet.find(lineSegSet[e.first.second].first.second));
                break;
            }
            case EVENT_VERTICAL:
            {
                // Iterate over all y values for intersecting horizontal lines
                multiset<int>:: const_iterator first, last, i;
                first = pEvSet.upper_bound(lineSegSet[e.first.second].second.second);
                last = pEvSet.lower_bound(lineSegSet[e.first.second].first.second);

                for (i = first; i != last; ++i) {
                     intersectionCounter++;
                }
                break;
            }
        }
    }

    cout << "Number of Intersections " << intersectionCounter << endl;
}